学步园

//思路：强连通分支然后重新构图，然后再判断出度为0的强连通分支里面的元素，如果出度为0的强连通有多个，则一定没有解！！

#include <iostream><br /> #include <string><br /> #include <vector><br /> #define maxn 10001<br /> using namespace std;<br /> int n,m,vis[maxn],ord[maxn],cnt,degree[maxn],out[maxn],ans;<br /> vector<int>G[maxn];<br /> vector<int>G1[maxn];<br /> void dfs(int u)<br /> {<br /> int i;<br /> vis[u] = 1;<br /> for(i = 0; i<G[u].size(); i++)<br /> if(!vis[G[u][i]])dfs(G[u][i]);<br /> ord[cnt++] = u;<br /> }<br /> void dfs1(int u)<br /> {<br /> int i;<br /> degree[u] = ans;<br /> vis[u] = 1;<br /> for(i = 0; i<G1[u].size(); i++)<br /> if(!vis[G1[u][i]])dfs1(G1[u][i]);<br /> }<br /> int main()<br /> {<br /> int i,u,v,j,p,sum,f;<br /> while(scanf("%d %d",&n,&m)!=EOF)<br /> {<br /> for(i = 1; i<=n; i++)<br /> {<br /> G[i].clear();<br /> G1[i].clear();<br /> }<br /> for(i = 0; i<m; i++)<br /> {<br /> scanf("%d %d",&u,&v);<br /> G[u].push_back(v);<br /> G1[v].push_back(u);<br /> }<br /> memset(out,0,sizeof(out));<br /> memset(vis,0,sizeof(vis));<br /> sum = p = ans = cnt = 0;<br /> for(i = 1; i<=n; i++)<br /> if(!vis[i])dfs(i);<br /> memset(vis,0,sizeof(vis));<br /> for(i = cnt - 1; i>=0; i--)<br /> if(!vis[ord[i]])<br /> {<br /> ans++;<br /> dfs1(ord[i]);<br /> }<br /> for(i = 1; i<=n; i++)<br /> for(j = 0; j<G[i].size(); j++)//找出度为0的点；<br /> {<br /> if(degree[i]!=degree[G[i][j]])<br /> {<br /> out[degree[i]]++;<br /> }<br /> }<br /> for(i = 1; i<=ans; i++)//标志出度为0的点，如果有多个点，此图肯定不连通<br /> if(out[i] == 0)<br /> {<br /> p++;<br /> f = i;<br /> }<br /> if(p>1)//不连通<br /> {<br /> printf("%d/n",0);<br /> continue;<br /> }<br /> for(i = 1; i<=n; i++)//度数为f强连通里面的数<br /> if(degree[i] == f)sum++;<br /> printf("%d/n",sum);<br /> }<br /> return 0;<br /> }