首页 > 代码库 > poj 2553 The Bottom of a Graph 【强连通图中出度为0点】
poj 2553 The Bottom of a Graph 【强连通图中出度为0点】
题目:poj 2553 The Bottom of a Graph
题意:大概题意是给出一个有向图,求强连通缩点以后出度为0的点。
分析:入门题目,先强连通缩点,然后表示出度为0的,枚举输出即可。
#include <cstdio> #include <vector> #include <iostream> #include <stack> #include <cstring> using namespace std; const int N = 25000; vector<int> G[N]; int pre[N],lowlink[N],sccno[N],dfs_clock,scc_cnt; //sccno【i】 i所在的scc图的编号 //scc_cnt 联通块的数量 stack<int> s; 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; if(x==u) break; } } } void find_scc(int n) { dfs_clock=scc_cnt=0; memset(sccno,0,sizeof(sccno)); memset(pre,0,sizeof(pre)); for(int i=0; i<n; i++) if(!pre[i]) dfs(i); } int in[N],out[N]; int flag[N]; vector<int> ans; void workout(int n) { memset(out,0,sizeof(out)); memset(flag,0,sizeof(flag)); for (int u = 0; u < n; u++) { for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; //printf("%d %d %d %d\n",u+1,v+1,sccno[u],sccno[v]); if (sccno[u] != sccno[v]) { out[sccno[u]] += 1; } } } for (int i = 1; i <= scc_cnt; i++) { if (out[i] == 0) flag[i] = 1; } for(int i=0;i<n;i++) { if(flag[sccno[i]]) ans.push_back(i+1); } for(int i=0;i<ans.size();i++) { printf("%d%c",ans[i],i==(ans.size()-1)?'\n':' '); } ans.clear(); } int main() { //freopen("Input.txt","r",stdin); int n,m,T; while(~scanf("%d",&n) && n) { scanf("%d",&m); for(int i=0;i<m;i++) { int x,y; scanf("%d%d",&x,&y); G[x-1].push_back(y-1); } find_scc(n); workout(n); for(int i=0;i<n;i++) G[i].clear(); } return 0; }
poj 2553 The Bottom of a Graph 【强连通图中出度为0点】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。