题意分析

裸题，输出scc的个数

代码总览

#include <bits/stdc++.h> using namespace std; const int nmax = 1e5 +10; const int INF = 0x3f3f3f3f; int low[nmax]; int dfn[nmax]; int sstack[nmax]; int head[nmax]; int color[nmax]; bool visit[nmax]; typedef struct{ int nxt,to; }Edge; Edge e[nmax]; int n,tot,top,dfnnum,sccnum; void add(int u, int v){ e[tot].to = v; e[tot].nxt = head[u]; head[u] = tot++; } void init(){ memset(head,-1,sizeof head); memset(visit,0,sizeof visit); n = tot = dfnnum = sccnum = 0; } void tarjan(int u){ low[u] = dfn[u] = ++dfnnum; visit[u] = true; sstack[++top] = u; for(int i = head[u] ; i != -1; i = e[i].nxt){ int v = e[i].to; if(!dfn[v]){ tarjan(v); low[u] = min(low[u],low[v]); }else if(visit[v]) low[u] = min(low[u], dfn[v]); } if(dfn[u] == low[u]){ visit[u] = false; color[u] = ++ sccnum; while(sstack[top] != u){ color[sstack[top]] = sccnum; visit[sstack[top]] = false; top--; } top--; } } int main(){ init(); scanf("%d",&n); int t; for(int i = 1;i<=n;++i) while(scanf("%d",&t) && t != 0) add(i,t); for(int i = 1;i<=n;++i) if(!dfn[i]) tarjan(i); printf("%d\n",sccnum); return 0; }