刚看的白书上的强连通,有种似懂非懂的感觉,所以就拿题目来练练手。
此题题意不说了。我们在求出强连通分量之后,答案就是唯一的那一个出度为0强连通分量之中的顶点个数。
#include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> #include <math.h> #include <stack> #include <vector> #define M 10005 using namespace std; int dfn[M],low[M],scc_cnt,index; int sccno[M]; stack<int> s; vector<int> G[M]; void Tarjan(int u) { dfn[u]=low[u]=++index; s.push(u); for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(!dfn[v]) { Tarjan(v); low[u]=min(low[u],low[v]); } else if(!sccno[v]) { low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]) { scc_cnt++; for(;;) { int x=s.top(); s.pop(); sccno[x]=scc_cnt; if(x==u) break; } } } void find_scc(int n) { index=scc_cnt=0; memset(sccno,0,sizeof(sccno)); memset(dfn,0,sizeof(dfn)); for(int i=0;i<n;i++) if(!dfn[i]) Tarjan(i); } int main() { int n,m; int out0[M]; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i<n;i++) G[i].clear(); for(int i=0;i<m;i++) { int u,v; scanf("%d%d",&u,&v); u--,v--; G[u].push_back(v); } find_scc(n); memset(out0,0,sizeof(out0)); int ans=0; for(int u=0;u<n;u++) { if(sccno[u]==1) //求一个强连通分量中的顶点个数 ans++; for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(sccno[u]!=sccno[v]) out0[sccno[u]]=1; } } int flag=0; for(int i=1;i<=scc_cnt;i++) //找出度为0的点的个数 { if(!out0[i]) flag++; } if(flag>1) printf("0\n"); else printf("%d\n",ans); } return 0; }