题目简述：一个有向图，求出这个图点数>1的强连通分量的个数。

那么就是tarjan求强联通分量的模板了。

记得要用一个数组标记节点是否在栈中。

1 #include
2 using namespace std;
3 const int N=1e5+10;
4 int head[N],nxt[N<<1],to[N<<1],tot; 5 int dfn[N],low[N],st[N],top,idx,cnt,sze[N]; 6 int n,m,a,b,ans; 7 bool vis[N];//标记节点是否在栈中 8 9 void add(int u,int v){ 10 nxt[++tot]=head[u]; 11 head[u]=tot; 12 to[tot]=v; 13 } 14 15 void tarjan(int u){ 16 low[u]=dfn[u]=++cnt; 17 st[++top]=u; 18 vis[u]=true; 19 for(int i=head[u];i;i=nxt[i]){ 20 int v=to[i]; 21 if(!dfn[v]){ 22 tarjan(v); 23 low[u]=min(low[u],low[v]); 24 } 25 else if(vis[v]){ 26 low[u]=min(low[u],dfn[v]); 27 } 28 } 29 if(low[u]==dfn[u]){ 30 int v; 31 idx++; 32 do{ 33 v=st[top--]; 34 sze[idx]++; 35 vis[v]=false; 36 }while(v!=u); 37 } 38 } 39 40 int main(){ 41 scanf("%d%d",&n,&m); 42 while(m--){ 43 scanf("%d%d",&a,&b); 44 add(a,b); 45 } 46 for(int i=1;i<=n;i++){ 47 if(!dfn[i]) tarjan(i); 48 } 49 int ans=0; 50 for(int i=1;i<=idx;i++){ 51 if(sze[i]>1) ans++;
52 }
53 printf("%d\n",ans);
54 }