题意:找强连通中点数大于2的强连通分量个数
思路:Tarjan// By SiriusRen #include#include using namespace std;int n,m,ans=0,t=0,cnt=0,tot=1,top=0,dfn[50050],low[50050],p[10050],s[10050];int xx,yy,jy,first[10050],next[50050],v[50050];bool vis[50050];void add(int x,int y){v[tot]=y;next[tot]=first[x];first[x]=tot++;}void tarjan(int x){ dfn[x]=low[x]=++cnt;vis[x]=1,s[++top]=x; for(int i=first[x];i;i=next[i]) if(!dfn[v[i]])tarjan(v[i]),low[x]=min(low[x],low[v[i]]); else if(vis[v[i]])low[x]=min(low[x],dfn[v[i]]); if(dfn[x]==low[x]){t++;do jy=s[top--],vis[jy]=0,p[t]++;while(jy!=x);}}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++)scanf("%d%d",&xx,&yy),add(xx,yy); for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i); for(int i=1;i<=n;i++)if(p[i]>=2)ans++; printf("%d\n",ans);}