[poj 2762]Going from u to v or from v to u?

发表于   |  

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

1
3 3
1 2
2 3
3 1

Sample Output

Yes

Source

POJ Monthly–2006.02.26,zgl & twb

Solution

题意： 一张无向图，判断图中的任意点对(x,y)是否全部存在y –> x或x –> y的路径。

也就是问图是否弱连通

一般做法是先tarjan强连通缩点，然后用拓扑判断一下。
要求锁点后的DAG全部联通（只有一个入度为0的点），并且没有分支（也就是删掉一个点后只能生成小于等于1的入度为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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#define MAXN 1001+1
#define MAXM 6000+1
using namespace std;
int e=0,edge=0,n,m,T,cnt,fir[MAXN],first[MAXN],tim=0,color[MAXN],dfn[MAXN],low[MAXN],inv[MAXN];
struct data{
	int nex,v;
}d[MAXM], a[MAXM];
void addedge(int u,int v){
	d[++e].v=v;
	d[e].nex=fir[u];
	fir[u]=e;
}
void addedge2(int u, int v){
	a[++edge].v = v;
	a[edge].nex = first[u];
	first[u] = edge;
}
stack <int> s;
bool ins[MAXN];
void tarjan(int u){
	dfn[u]=low[u]=++tim;
	s.push(u);
	ins[u] = true;
	for (int i=fir[u];i;i=d[i].nex){
		int v=d[i].v;
		if (!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		} else {
			if (ins[v]) low[u]=min(low[u],dfn[v]);
		}
	}
	if (dfn[u]==low[u]){
		++cnt;
		int v;
		do{
			v=s.top();
			color[v]=cnt;
			s.pop();
			ins[v] = false;
		} while (u!=v);
	}
}

void makeDAG(){
	for (int i=1;i<=n;i++){
		if (!dfn[i]) tarjan(i);
	}
	//for (int i=1;i<=n;i++) printf(""%d "",color[i]);
	//printf(""\n"");
	for (int u = 1; u <= n; u++){
		for (int i = fir[u]; i; i = d[i].nex){
			int v = d[i].v;
			if (color[u] != color[v]){
				addedge2(color[u], color[v]);
				//cout<<color[u]<<color[v]<<endl;
				inv[color[v]]++;
			}
		}
	}
}
queue <int> q;
bool inq[MAXN];
bool topo(){
	for (int u = 1; u <= cnt; u++)
		if (inv[u] == 0) {
			q.push(u);
			inq[u]=true;
		}		
	//cout<<""size""<<q.size()<<endl;
	if (q.size() > 1) return false;
	while (!q.empty()){
		int u = q.front();
		q.pop();
		int cnt = 0;
		for (int i = first[u]; i; i = a[i].nex){
			int v = a[i].v;
			if (inq[v]) continue;
			if (!--inv[v]){
				cnt++;
				if (cnt >= 2) return false;
				q.push(v);
				inq[v] = true;
			}
		}
	}
	return true;
}

inline void clear(){
	memset(dfn,0,sizeof dfn);
	memset(low,0,sizeof low);
	memset(color,0,sizeof color);
	memset(ins,0,sizeof ins);
	memset(inq,0,sizeof inq);
	memset(inv,0,sizeof inv);
	memset(first, 0, sizeof first);
	memset(fir, 0, sizeof fir);
	memset(d, 0, sizeof d);
	memset(a, 0, sizeof a);	
	while (!q.empty()) q.pop();
	while (!s.empty()) s.pop();
	e=0;tim=0;cnt=0;edge = 0;
}

int main(){
	freopen(""in.txt"",""r"",stdin);
	freopen(""out.txt"",""w"",stdout);
	scanf(""%d"",&T);
	while (T--){
		scanf(""%d%d"",&n,&m);
		clear();	
		for (int i=1;i<=m;i++){
			int u,v;
			scanf(""%d%d"",&u,&v);
			addedge(u,v);
		}
		makeDAG();
		if (topo()) puts(""Yes"");
		else puts(""No"");
	}
}