缩点裸题。
题目链接：http://poj.org/problem?id=2186
正确板子是 ：1.缩点之后无需在意各连通块的大小，只需找出所有连通块都经过的那一个连通块；
2.最后只需：有且仅有一个点(连通块)出度为0，则输出该点大小；其他情况一律输出0。
（依据：①有向图缩点之后成为有向无环图；
②有向无环图中必有出度为0的点 + 若只有一个出度为0的点，则所有点都可到达该点；
③若有向无环图中有多个出度为0的点，则不存在 所有点都可到达的点。）
自己用的深搜找那个所有点都可到达的点，但有谜：为何是>=n？何时重复了？
#include<iostream> #include<cstdio> using namespace std; int n,m,x,y,xnt,nex[10005],rd[10005],cd[10005],dfn[10005],low[10005],sc[10005]; int tim,s,in[10005],cnt,col[10005],siz,gs[10005]; bool vis[10005],sid[10005][10005],flag[10005]; struct Node{ int next,to,from; }edge[50005]; void add(int x,int y) { xnt++; edge[xnt].next=nex[x]; edge[xnt].to=y; edge[xnt].from=x; nex[x]=xnt; } void tar(int a) { for(int i=nex[a];i;i=edge[i].next) { int v=edge[i].to; if(!dfn[v]) { dfn[v]=++tim; low[v]=dfn[v]; vis[v]=1; in[++cnt]=v; tar(v); if(low[v]<low[a]) low[a]=low[v]; } else if(vis[v]) if(low[v]<low[a])low[a]=low[v];//找最早的 } if(dfn[a]==low[a]) { siz++; int k=0; while(1) { k++; col[in[cnt]]=siz; vis[in[cnt]]=0; cnt--; if(in[cnt+1]==a)break; } sc[siz]=k; gs[siz]=k; } } void ser(int str,int zs) { int k=zs; if(!flag[str]) { flag[str]=1; zs+=sc[str]; } sc[str]+=k; if(!cd[str])return; for(int i=1;i<=siz;i++) if(sid[str][i])ser(i,zs); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); add(x,y); } for(int i=1;i<=n;i++) if(!dfn[i]) { cnt=1; dfn[i]=++tim; low[i]=dfn[i]; vis[i]=1; in[1]=i; tar(i); } for(int i=1;i<=m;i++) { int u=edge[i].from; int v=edge[i].to; if(col[u]!=col[v]) { sid[col[u]][col[v]]=1;//col[u] rd[col[v]]++; cd[col[u]]++; } } // for(int i=1;i<=siz;i++)//90 深搜 // if(!rd[i]) // ser(i,0); // for(int i=1;i<=siz;i++) // if(sc[i]>=n) //由==改为>=则100 // s+=gs[i]; // for(int i=1;i<=siz;i++)//85 // if(!cd[i])s+=gs[i]; int uu=0;int kk=0;//100 结论 for(int i=1;i<=siz;i++) if(!cd[i])uu++,kk=i; if(uu==1)printf("%d",gs[kk]); else printf("0"); // printf("%d",s); return 0; }