18.11.08 POJ 2762 Going from u to v or from v to u?(强连通+
描述 In order to make their sons brave,Jiajia and Wind take them to a big cave. The cave has n rooms,and one-way corridors connecting some rooms. Each time,Wind choose two rooms x and y,and ask one of their little sons go from one to the other. The son can either go from x to y,or from y to x. Wind promised that her tasks are all possible,but she actually doesn‘t know how to decide if a task is possible. To make her life easier,Jiajia decided to choose a cave in which every pair of rooms is a possible task. Given a cave,can you tell Jiajia whether Wind can randomly choose two rooms without worrying about anything? 输入 The first line contains a single integer T,the number of test cases. And followed T cases. 样例输入 1
3 3
1 2
2 3
3 1
样例输出 Yes
1 #include <iostream> 2 #include <string.h> 3 #include <algorithm> 4 #include <stack> 5 #include <string> 6 #include <math.h> 7 #include <queue> 8 #include <stdio.h> 9 #include <string.h> 10 #include <vector> 11 #include <fstream> 12 #include <set> 13 14 using namespace std; 15 16 const int maxn = 1005; 17 vector<vector<int>>G(maxn); 18 vector<set<int>>DAG(maxn); 19 int dfn[maxn],low[maxn],father[maxn],colorP[maxn]; 20 bool route[maxn]; 21 int to[maxn]; 22 int ncount = 1,n,m,color; 23 stack<int>p; 24 25 void tarjan(int u,int father) { 26 route[u] = true; 27 p.push(u); 28 low[u] = dfn[u] = ncount++; 29 int l = G[u].size(); 30 for (int i = 0; i < l; i++) { 31 int next = G[u][i]; 32 if (!dfn[next]) 33 tarjan(next,u); 34 else if(route[next]) 35 low[u] = min(low[u],low[next]); 36 } 37 if (dfn[u] == low[u]) { 38 int v = 0; 39 ++color; 40 while (v != u) { 41 v = p.top(); 42 p.pop(); 43 colorP[v] = color; 44 } 45 } 46 route[u] = false; 47 } 48 49 bool top() { 50 int id,sum = 0; 51 for (int i = 1; i <= color; i++) { 52 if (to[i] == 0) { 53 id = i; 54 sum++; 55 } 56 } 57 while (sum!=0) 58 { 59 if (sum > 1) 60 return false; 61 sum = 0; 62 set<int>::iterator i1 = DAG[id].begin(),i2 = DAG[id].end(); 63 for (; i1 != i2; i1++) 64 { 65 to[*i1]--; 66 if (to[*i1] == 0) { 67 id = *i1; 68 sum++; 69 } 70 } 71 } 72 return true; 73 } 74 75 void calculate() { 76 for (int i = 1; i <= n; i++) { 77 int size = G[i].size(); 78 for (int j = 0; j < size; j++) { 79 int v = G[i][j]; 80 if (colorP[v] != colorP[i]) 81 { 82 DAG[i].insert(colorP[v]); 83 to[colorP[v]]++; 84 } 85 } 86 } 87 if (top()) 88 printf("Yesn"); 89 else 90 printf("Non"); 91 } 92 93 void init() { 94 int kase; 95 scanf("%d",&kase); 96 while (kase--) 97 { 98 ncount = 1,n=0,m=0,color=0; 99 memset(to,0,sizeof(to)); 100 memset(dfn,sizeof(to)); 101 memset(low,sizeof(to)); 102 memset(father,sizeof(to)); 103 memset(colorP,sizeof(to)); 104 G = vector<vector<int>>(maxn); 105 DAG = vector<set<int>>(maxn); 106 scanf("%d%d",&n,&m); 107 while (m--) { 108 int from,to; 109 scanf("%d%d",&from,&to); 110 G[from].push_back(to); 111 father[to] = from; 112 } 113 for (int i = 1; i <= n; i++) { 114 if (!dfn[i]) 115 tarjan(i,father[i]); 116 } 117 calculate(); 118 } 119 } 120 121 int main() 122 { 123 init(); 124 return 0; 125 } 这道题给的数据也相当水,比较迷的是我在openjudge上跑了1ms,在POJ永远TLE 属于玄学过的,之后再到POJ跑跑看(我说的之后再看看好像就没看过……唉……) 思路是拓扑排序,首先是确定对有向无环图来说符合两点两两相通的情况必须是只有一个点入度为0且只有一个点出度为0并且没有分叉点 不知道老师课上有没有讲过,网上的参考,贴一下
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |