https://www.luogu.org/problem/P2863

#include<cstdio> #include<vector> using namespace std; int dfn[10005],low[10005],stack[10005],scc[10005],num[10005],vis[10005]; int clock,scc_cnt,top; vector<int>e[10005]; inline void dfs_scc(int x) { dfn[x]=low[x]=++clock;//访问次序标记；x能到的祖先中节点编号最小的 stack[++top]=x;//把走过的节点入栈 vis[x]=1; for(int i=0;i<e[x].size();i++) { int now=e[x][i]; if(!dfn[now])//如果没有被访问过 { dfs_scc(now);//进它 low[x]=min(low[x],low[now]);//既然now是x的子节点，那么他们一定有公告的祖先，取个小的 } else if(vis[now])//如果他还没有被其他强连通分量使用 low[x]=min(low[x],dfn[now]);//那么再小一点 } if(low[x]==dfn[x]) { scc_cnt++; while(stack[top]!=x) { //x节点在栈中夹着的节点就是强连通分量的节点 scc[stack[top--]]=scc_cnt; vis[stack[top+1]]=0; num[scc_cnt]++; }//哪一个点在当前编号为scc_cnt的强连通分量里 top--; vis[x]=0; num[scc_cnt]++; scc[x]=scc_cnt;//一个强连通分量 } } int main() { int n,m,a,b; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); e[a].push_back(b); //e[b].push_back(a); } int ans=0; for(int i=1;i<=n;i++) { if(dfn[i]==0) { dfs_scc(i); } } for(int i=1;i<=scc_cnt;i++) { if(num[i]>1) { ans++; } } printf("%d\n",ans); return 0; }