http://poj.org/problem?id=3180
英文题以后都不粘贴题面。
大意：求点数大于1的强连通分量个数
#include<stack> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; inline int read(){ int x=0,w=1;char ch=0; while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*w; } const int maxn=10001; int cnt=0,head[maxn]; struct node{ int w; int to; int nxt; }edge[50001]; void add(int u,int v){ cnt++; edge[cnt].to=v; edge[cnt].nxt=head[u]; head[u]=cnt; return; } int dfn[maxn]; int low[maxn]; bool instack[maxn]; int dis[maxn]; int ans=0; int t=0; stack<int>q; void tarjan(int u){ int v; t++; dfn[u]=t; low[u]=t; q.push(u); instack[u]=1; for(int i=head[u];i!=0;i=edge[i].nxt){ v=edge[i].to; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); }else if(instack[v]){ low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]){ int k=0; do{ v=q.top(); q.pop(); instack[v]=0; k++; }while(v!=u); if(k>=2)ans++; } return; } int main(){ int n=read(); int m=read(); for(int i=1;i<=m;i++){ int u=read(); int v=read(); add(u,v); } for(int i=1;i<=n;i++){ if(!dfn[i]){ tarjan(i); } } printf("%d ",ans); return 0; }