Going from u to v or from v to u?
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 15755 | Accepted: 4172 |
Description
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
13 31 22 33 1
Sample Output
Yes
题意:是给出一些点，给出n个点和m条边,接着给出直接相连的边(注意是有向边),求解随意x,y两点间是否存在 x 可到达 y 或者y可
到达x,假设随意x和y都满足这种条件,就输出"Yes", 否则输出"No".。注意。这里是 x 到达 y 或者 y 到达 x ，是或者不是并且 。！
。
假设是“并且”的话。非常明显的是推断整个图是否为一个强连通分量（如题HDU 1296 , ）。但这题并非这样。
本题应推断整个图是否为一个弱连通分量。
正确思路：先求解出该有向图的强连通分量。然后依据求解出来的强连通分量进行缩点又一次建图
问题转换为求解在新图中是否存在一条能走全然部的顶点的路径，这时能够对缩点后的新图进行拓扑排序，看拓扑排序能否够成功进行。
拓扑排序遵循条件
一：新图不能有多于1个的入度为0的点，这是保证每一个点都有边相连。 二：在拓扑排序遍历点u的过程中，若去掉与u相关的边后出现多于1个的入度为0的点，说明这些点仅仅能由u到达，而它们之间不存在可达路径。这时不满足弱连通，跳出。#include#include #include #include #include #define maxn 10000 + 100#define maxm 100000 + 1000using namespace std;int n, m;struct node { int u, v, next;};node edge[maxm];int head[maxn], cnt;int low[maxn], dfn[maxn];int dfs_clock;int Stack[maxn];bool Instack[maxn];int top;int Belong[maxn] , scc_clock;int in[maxn];vector Map[maxn];void init(){ cnt = 0; memset(head, -1, sizeof(head));}void addedge(int u, int v){ edge[cnt] = {u, v, head[u]}; head[u] = cnt++;}void getmap(){ scanf("%d%d", &n, &m); while(m--){ int a, b; scanf("%d%d", &a, &b); addedge(a, b); }}void tarjan(int u, int per){ int v; low[u] = dfn[u] = ++dfs_clock; Stack[top++] = u; Instack[u] = true; for(int i = head[u]; i != -1; i = edge[i].next){ v = edge[i].v; if(!dfn[v]){ tarjan(v, u); low[u] = min(low[v], low[u]); } else if(Instack[v]){ low[u] = min(low[u], dfn[v]); } } if(dfn[u] == low[u]){ scc_clock++; do{ v = Stack[--top]; Instack[v] = false; Belong[v] = scc_clock; }while(u != v); }}void find(){ memset(low, 0, sizeof(low)); memset(dfn, 0, sizeof(dfn)); memset(Instack, false, sizeof(Instack)); memset(Belong, 0, sizeof(Belong)); dfs_clock = scc_clock = top = 0; for(int i = 1; i <= n; ++i){ if(!dfn[i]) tarjan(i, i); }}void suodian(){ for(int i = 1; i <= scc_clock; ++i){ Map[i].clear(); in[i] = 0; } for(int i = 0; i < cnt; ++i){ int u = Belong[edge[i].u]; int v = Belong[edge[i].v]; if(u != v){ Map[u].push_back(v); in[v]++; } }}void solve(){ queue q; int num = 0; for(int i = 1; i <= scc_clock; ++i){ if(!in[i]){ num++; q.push(i); } if(num > 1){ printf("No\n"); return ; } } while(!q.empty()){ int u = q.front(); q.pop(); num = 0; for(int i = 0; i < Map[u].size(); ++i){ int v = Map[u][i]; in[v]--; if(!in[v]){ num++; //有两个或两个以上的分支。不是弱连通 if(num > 1){ printf("No\n"); return ; } q.push(v); } } } printf("Yes\n");}int main (){ int T; scanf("%d", &T); while(T--){ init(); getmap(); find(); suodian(); solve(); } return 0;}