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?
Input
The first line contains a single integer T, the number of test cases. And followed T cases.
The first line for each case contains two integers n, m(0 < n < 1001,m < 6000), the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly.
Output
The output should contain T lines. Write 'Yes' if the cave has the property stated above, or 'No' otherwise.
Sample Input
1
3 3
1 2
2 3
3 1
Sample Output
Yes
Source
POJ Monthly--2006.02.26,zgl & twb
题目类型：有向图强连通分量(Tarjan) +缩点+拓扑排序判定
算法分析：这个题目要判断一个图是否是单连通的，由于图中同一个强连通分量中的点一定是单连通的，所以可以不用考虑同一个强连通分量中的所有点之间的连通情况继而将其缩成一个点。然后考察缩完点之后的图，易知这个图任意两点之间最多单向可达。由于处理后得到的图仍然是有向图，所以可以对图进行拓扑排序。对于得到的拓扑序列，相邻的节点要么是”非同层”顶点，要么是”同层”顶点(拓扑排序过程中某次入度为0的顶点之间互为”同层”顶点)。对于以上两种情况，只要满足拓扑序中所有相邻的顶点之间邻接，则由传递性可知，每个顶点之间都可达
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 |
/************************************************* Author :supermaker Created Time :2016/1/22 19:11:57 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1000 + 66; int dfn[maxn], low[maxn], belong[maxn]; bool instack[maxn]; stack <int> sta; vector <int> g[maxn]; int n, m, id, tot; int gg[maxn][maxn], indeg[maxn], topo[maxn]; void Init () { for (int i = 0; i < maxn; i++) g[i].clear (); } void dfs (int u) { dfn[u] = low[u] = ++id; sta.push (u); instack[u] = true; for (int i = 0; i < g[u].size (); i++) { int v = g[u][i]; if (!dfn[v]) { dfs (v); low[u] = min (low[u], low[v]); } else if (instack[v]) low[u] = min (low[u], dfn[v]); } if (low[u] == dfn[u]) { tot++; int tt; do { tt = sta.top (); sta.pop (); instack[tt] = false; belong[tt] = tot; } while (!sta.empty () && tt != u); } } void SS () { memset (dfn, 0, sizeof (dfn)); memset (low, 0, sizeof (low)); memset (instack, false, sizeof (instack)); while (!sta.empty ()) sta.pop (); tot = id = 0; for (int i = 1; i <= n; i++) if (!dfn[i]) dfs (i); } int main() { //CFF; //CPPFF; int t; scanf ("%d", &t); while (t--) { Init (); scanf ("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int u, v; scanf ("%d%d", &u, &v); g[u].push_back (v); } SS (); memset (gg, 0, sizeof (gg)); memset (indeg, 0, sizeof (indeg)); for (int u = 1; u <= n; u++) for (int i = 0; i < g[u].size (); i++) { int v = g[u][i]; if (belong[u] != belong[v]) { gg[belong[u]][belong[v]] = 1; indeg[belong[v]]++; } } queue <int> qua; for (int i = 1; i <= tot; i++) if (!indeg[i]) qua.push (i); int len = 0; while (!qua.empty ()) { int u = qua.front (); qua.pop (); topo[++len] = u; for (int v = 1; v <= tot; v++) if (u != v && gg[u][v]) { indeg[v]--; if (!indeg[v]) qua.push (v); } } bool is_valid = true; for (int i = 1; i <= tot - 1; i++) if (!gg[topo[i]][topo[i+1]]) { is_valid = false; break; } if (is_valid) puts ("Yes"); else puts ("No"); } return 0; } |
- « 上一篇：poj3177
- poj2186：下一篇 »