首页 > 代码库 > POJ 2762 Going from u to v or from v to u? （判断弱连通）
POJ 2762 Going from u to v or from v to u? （判断弱连通）
http://poj.org/problem?id=2762
题意：
给出有向图，判断任意两个点u和v，是否可以从u到v或者从v到u。
思路：
判断图是否是弱连通的。
首先来一遍强连通缩点，重新建立新图，接下来我们在新图中找入度为0的点，入度为0的点只能有1个，如果有多个那么这些个点肯定是不能相互到达的。
如果只有一个入度为0的点，走一遍dfs判断新图是否是单链，如果有分支，那么分支上的点肯定是不能相互到达的。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<stack> 7 #include<queue> 8 #include<cmath> 9 #include<map> 10 using namespace std; 11 typedef long long LL; 12 13 const int maxn=6000+5; 14 15 int n,m; 16 17 int x[maxn],y[maxn]; 18 int in[maxn]; 19 int flag; 20 21 vector<int> G[maxn]; 22 vector<int> new_G[maxn]; 23 24 stack<int> S; 25 int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt; 26 27 void dfs(int u) 28 { 29 pre[u] = lowlink[u] = ++dfs_clock; 30 S.push(u); 31 for (int i = 0; i < G[u].size(); i++) 32 { 33 int v = G[u][i]; 34 if (!pre[v]) 35 { 36 dfs(v); 37 lowlink[u] = min(lowlink[u], lowlink[v]); 38 } 39 else if(!sccno[v]) 40 lowlink[u] = min(lowlink[u], pre[v]); 41 } 42 if (pre[u] == lowlink[u]) 43 { 44 scc_cnt++; 45 for(;;) 46 { 47 int x = S.top(); S.pop(); 48 sccno[x] = scc_cnt; 49 if (x == u) break; 50 } 51 } 52 } 53 54 void find_scc(int n) 55 { 56 dfs_clock = scc_cnt = 0; 57 memset(pre, 0, sizeof(pre)); 58 memset(sccno, 0, sizeof(sccno)); 59 for (int i = 1; i <= n; i++) 60 if (!pre[i]) dfs(i); 61 } 62 63 64 void dfs2(int u) 65 { 66 if(flag==0) return; 67 if(new_G[u].size()>1) {flag=0;return;} 68 if(new_G[u].size()!=0) dfs2(new_G[u][0]); 69 } 70 71 72 void rebulid() 73 { 74 for(int i=1;i<=scc_cnt;i++) {new_G[i].clear();in[i]=0;} 75 for(int i=0;i<m;i++) 76 { 77 if(sccno[x[i]]!=sccno[y[i]]) 78 { 79 new_G[sccno[x[i]]].push_back(sccno[y[i]]); 80 in[sccno[y[i]]]=1; 81 } 82 } 83 int num=0; 84 int pos; 85 for(int i=1;i<=scc_cnt;i++) 86 { 87 if(in[i]==0) {num++;pos=i;} 88 if(num>=2) {flag=0;return;} 89 } 90 if(flag) dfs2(pos); 91 } 92 93 int main() 94 { 95 //freopen("D:\\input.txt","r",stdin); 96 int T; 97 scanf("%d",&T); 98 while(T--) 99 {100 flag=1;101 scanf("%d%d",&n,&m);102 for(int i=1;i<=n;i++) G[i].clear();103 for(int i=0;i<m;i++)104 {105 scanf("%d%d",&x[i],&y[i]);106 G[x[i]].push_back(y[i]);107 }108 find_scc(n);109 rebulid();110 if(flag) puts("Yes");111 else puts("No");112 }113 return 0;114 }
POJ 2762 Going from u to v or from v to u? （判断弱连通）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。