好吧，可能有人是WA了找题解看…这么裸的题，WA的话估计只有一个问题没注意到，可能不止一个图…又没说这个是一个大的联通块…我就这个地方卡了好久233，可能是我太弱
这题题目贼长233，要看背景就自己看嘛 题目： https://vjudge.net/problem/POJ-3180 反正就是问这个图里面大小大于等于2的强连通分量有多少个
直接上代码了
#include<iostream> #include<cstring> #include<cstdio> #define MAXN 50000+10 using namespace std; struct Line{ int from,to,next; }line[MAXN]; int head[MAXN],tail,cnt,low[MAXN],dfn[MAXN],timer,vis[MAXN],stack[MAXN],top,N,M; void tarjan(int x){ dfn[x]=++timer; low[x]=timer; vis[x]=true; stack[++top]=x; for(register int i=head[x];i;i=line[i].next){ int temp=line[i].to; if(!dfn[temp]){ tarjan(temp); low[x]=min(low[x],low[temp]); }else{ if(vis[temp]) low[x]=min(low[x],dfn[temp]); } } if(dfn[x]==low[x]){ vis[x]=false; int temp=0; while(stack[top]!=x){ vis[stack[top]]=false; top--;temp++; } if(temp) cnt++; top--; } } void add_line(int from,int to){ tail++; line[tail].from=from; line[tail].to=to; line[tail].next=head[from]; head[from]=tail; } void solve(){ for(int i=1;i<=N;i++){ if(!low[i]) tarjan(i); } } int main(){ scanf("%d%d",&N,&M); for(register int i=1;i<=M;i++){ int f,t; scanf("%d%d",&f,&t); add_line(f,t); } solve(); printf("%d",cnt); return 0; }