解题思路:
本题要求 求出所有满足“自己可达的顶点都能到达自己”的顶点个数,并从小到大输出。 利用Tarjan算法求出强连通分量,统计每个强连通分量的出度,出度为0的强连通分量内的顶点即为所求顶点。
#include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <algorithm> #include <cmath> #include <vector> #include <queue> #include <set> #include <stack> #define ll long long #define ull unsigned long long using namespace std; const int maxn = 5000 + 50; vector<int> G[maxn]; int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt; stack<int> s; int out[maxn]; vector<int> num[maxn]; int ans[maxn]; void dfs(int u) { pre[u] = lowlink[u] = ++dfs_clock; s.push(u); for(int i=0;i<G[u].size();i++) { int v = G[u][i]; if(!pre[v]) { dfs(v); lowlink[u] = min(lowlink[u],lowlink[v]); } else if(!sccno[v]) { lowlink[u] = min(lowlink[u],pre[v]); } } if(lowlink[u] == pre[u]) { scc_cnt++; for(;;) { int x = s.top(); s.pop(); sccno[x] = scc_cnt; num[scc_cnt].push_back(x); if(x == u) break; } } } void find_scc(int n) { dfs_clock = scc_cnt = 0; memset(sccno,0,sizeof(sccno)); memset(pre,0,sizeof(pre)); memset(num,0,sizeof(num)); memset(ans,0,sizeof(ans)); memset(out,0,sizeof(out)); for(int i=1;i<=n;i++) { if(!pre[i]) dfs(i); } for(int i=1;i<=n;i++) { int sz = G[i].size(); for(int j=0;j<sz;j++) { if(sccno[i] != sccno[G[i][j]]) { out[sccno[i]] = 1; } } } int c = 0; for(int i=1;i<=scc_cnt;i++) { if(out[i] == 0) { int sz = num[i].size(); for(int j=0;j<sz;j++) { ans[++c] = num[i][j]; } } } if(!c) cout<<endl; sort(ans+1,ans+1+c); for(int i=1;i<c;i++) printf("%d ",ans[i]); printf("%d\n",ans[c]); } int N , M; int main() { while(scanf("%d",&N)!=EOF && N) { scanf("%d",&M); int u , v; for(int i=1;i<=N;i++) {G[i].clear();num[i].clear();} for(int i=1;i<=M;i++) { scanf("%d%d",&u,&v); G[u].push_back(v); } find_scc(N); } }
POJ 2553 The Bottom of a Graph(Tarjan,强连通分量),布布扣,bubuko.com
POJ 2553 The Bottom of a Graph(Tarjan,强连通分量)
原文:http://blog.csdn.net/moguxiaozhe/article/details/38441073