tarjan强连通分量求缩点重构图，出度为0的点若只有一个则输出其代表强连通分量的大小，否则无解。
因为一旦出度为0就没人被他认为长得帅
1 /* 2 ID:WULALA 3 PROB:bzoj1051 4 LANG:C++ 5 */ 6 #include7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #define N 10008 14 #define M 50008 15 #define mod 16 #define mid(l,r) ((l+r) >> 1) 17 #define INF 0x7ffffff 18 using namespace std; 19 20 int n,m,dfn[N],low[N],que[N],head[N],cnt,h[N],scc,belong[N],ans,hav[N],r; 21 bool vis[N],inq[N],flag; 22 23 struct WULALA 24 { 25 int node,next; 26 }e[M],d[M]; 27 28 void init() 29 { 30 scanf("%d%d",&n,&m); 31 for (int i = 1;i <= m;i++) 32 { 33 int x,y; 34 scanf("%d%d",&x,&y); 35 e[i].node = y; 36 e[i].next = head[x]; 37 head[x] = i; 38 } 39 } 40 41 void dfs(int a) 42 { 43 vis[a] = true; 44 low[a] = dfn[a] = ++cnt; 45 inq[a] = true; que[++r] = a; 46 int c = head[a]; 47 while(c) 48 { 49 if (!vis[e[c].node]) 50 { 51 dfs(e[c].node); 52 low[a] = min(low[a],low[e[c].node]); 53 } 54 else if (inq[e[c].node]) low[a] = min(low[a],dfn[e[c].node]);//要判是否在队列里！！ 55 c = e[c].next; 56 } 57 if (low[a] == dfn[a]) 58 { 59 belong[a] = ++scc; 60 hav[scc] = 1; 61 while (que[r] != a) 62 { 63 belong[que[r]] = scc; 64 inq[que[r]] = false; 65 ++hav[scc]; 66 --r; 67 } 68 inq[que[r]] = false;//!!! 69 --r;//!!! 70 } 71 } 72 73 void rebuild() 74 { 75 cnt = 0; 76 for (int i = 1;i <= n;i++) 77 { 78 int c = head[i]; 79 while(c) 80 { 81 if (belong[i] != belong[e[c].node]) 82 { 83 d[++cnt].node = belong[e[c].node]; 84 d[cnt].next = h[belong[i]]; 85 h[belong[i]] = cnt; 86 } 87 c = e[c].next; 88 } 89 } 90 } 91 92 void tarjan() 93 { 94 95 for (int i = 1;i <= n;i++) 96 if (!vis[i]) dfs(i); 97 rebuild(); 98 } 99 100 void work()101 {102 for (int i = 1;i <= scc;i++)103 if (!h[i])104 {105 if (ans)106 {107 ans = 0;108 return;109 }110 else ans = hav[i];111 }112 }113 114 int main()115 {116 init();117 tarjan();118 work();119 printf("%d\n",ans);120 return 0;121 }