几乎是板子, 求有几个 size>1 的 scc
直接 tarjan 即可
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- using namespace std;
- const int N=10005;
- int n,m,h[N],cnt,ans,tmp,dfn[N],low[N],s[N],top;
- bool v[N];
- struct qwe
- {
- int ne,to;
- }e[N*10];
- int read()
- {
- int r=0,f=1;
- char p=getchar();
- while(p>'9'||p<'0')
- {
- if(p=='-')
- f=-1;
- p=getchar();
- }
- while(p>='0'&&p<='9')
- {
- r=r*10+p-48;
- p=getchar();
- }
- return r*f;
- }
- void add(int u,int v)
- {
- cnt++;
- e[cnt].ne=h[u];
- e[cnt].to=v;
- h[u]=cnt;
- }
- void tarjan(int u)
- {
- dfn[u]=low[u]=++tmp;
- v[s[++top]=u]=1;
- for(int i=h[u];i;i=e[i].ne)
- {
- if(!dfn[e[i].to])
- {
- tarjan(e[i].to);
- low[u]=min(low[u],low[e[i].to]);
- }
- else if(v[e[i].to])
- low[u]=min(low[u],dfn[e[i].to]);
- }
- if(low[u]==dfn[u])
- {
- int sum=0;
- while(s[top]!=u)
- {
- v[s[top--]]=0;
- sum++;
- }
- v[s[top--]]=0;
- if(sum)
- ans++;
- }
- }
- int main()
- {
- n=read(),m=read();
- for(int i=1;i<=m;i++)
- {
- int x=read(),y=read();
- add(x,y);
- }
- for(int i=1;i<=n;i++)
- if(!dfn[i])
- tarjan(i);
- printf("%d",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2593841.html