【POJ - 2762】Going from u to v or from v to u?（Tarjan缩点，树形dp 或拓扑排序，欧拉图相关）

题干：

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

Sample Output

Yes

题目大意：

问一个图是否是单连通的。

解题报告：

先对全图求一次SCC，可以知道每个SCC内的点都是单连通的，那么把每个SCC缩点构建出DAG之后再判断这个DAG是否单连通即可。方法不唯一：可以是拓扑排序，看他每次是否只有一个活跃点就可以了，如果不是一个，那肯定不符合要求。

第二种方法：是DAG动规找出最长链，如果最长链上的点个数等于SCC个数，那么DAG单连通。（因为如果最长链都不能覆盖所有点，那么必定有两个点之间是无法到达的）

刚开始以为直接判断是否是一条链就行了，后来3 -> 1、 1 -> 2、3 -> 2这组数据就Hack掉了，，本应该是Yes，但是这样肯定就是No了。然后想判一个欧拉通路，虽然可以AC，但是有数据是过不了的。（数据水了）

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 1000 + 5;
struct Edge {
	int fr,to,ne;
} e[6005],E[6005];
vector<int> vv[MAX];
int head[MAX],HEAD[MAX],tot,TOT;
bool ok[MAX][MAX];
void add(int u,int v) {
	e[++tot].to = v;
	e[tot].fr = u;
	e[tot].ne = head[u];
	head[u] = tot;
}
int n,m;
int DFN[MAX],LOW[MAX],scc,clk,index,sk[MAX],vis[MAX],col[MAX],in[MAX],out[MAX]; 
void Tarjan(int x) {
	DFN[x] = LOW[x] = ++clk;
	vis[x]=1;
	sk[++index] = x;
	for(int i = head[x]; ~i; i = e[i].ne) {
		int v = e[i].to;
		if(DFN[v] == 0) {
			Tarjan(v);
			LOW[x] = min(LOW[x],LOW[v]);
		}
		else if(vis[v]) {
			LOW[x] = min(LOW[x],DFN[v]);
		}		
	}
	if(LOW[x] == DFN[x]) {
		scc++;
		while(1) {
			int tmp = sk[index];index--;
			vis[tmp]=0;
			col[tmp] = scc;
			if(tmp == x) break;
		}				
	}	
}
void init() {
	scc=clk=tot=TOT=index=0;
	for(int i = 1; i<=n; i++) {
		vv[i].clear();
		head[i] = HEAD[i] = -1;
		vis[i] = DFN[i] = LOW[i] = in[i] = out[i] = 0;
	}
	for(int i = 1; i<=n; i++) {
		for(int j = 1; j<=n; j++) ok[i][j]=0;
	}
}
bool topu() {
	queue<int> q;
	for(int i = 1; i<=scc; i++) {
		if(in[i] == 0)  q.push(i);
	}
	int cnt = 0;
	while(!q.empty()) {
		if(q.size() > 1) return 0 ;
		int cur = q.front();q.pop();
		cnt++;
		int up = vv[cur].size();
		for(int i = 0; i<up; i++) {
			int v = vv[cur][i];
			in[v]--;
			if(in[v] == 0) q.push(v);
		}		
	}
	return cnt == scc;
}
int main()
{
	int t;
	cin>>t;
	while(t--) {
		scanf("%d%d",&n,&m);		
		init();
		for(int a,b,i = 1; i<=m; i++) {
			scanf("%d%d",&a,&b);
			add(a,b);
		}
		for(int i = 1; i<=n; i++) {
			if(DFN[i] == 0) Tarjan(i);
		}
		for(int a,b,i = 1; i<=tot; i++) {
			a=col[e[i].fr],b=col[e[i].to];
			if(a==b) continue;
			if(ok[a][b]) continue;
			ok[a][b]=1;
			in[b]++;
			out[a]++;
			vv[a].pb(b);
		}
		bool flag = topu();
		if(flag) puts("Yes");
		else puts("No");
	}


	return 0 ;
}

AC代码：（树形dp）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 1000 + 5;
struct Edge {
	int fr,to,ne;
} e[6005],E[6005];
vector<int> vv[MAX];
int head[MAX],HEAD[MAX],tot,TOT;
bool ok[MAX][MAX];
void add(int u,int v) {
	e[++tot].to = v;
	e[tot].fr = u;
	e[tot].ne = head[u];
	head[u] = tot;
}
int n,m;
int dp[MAX];
int DFN[MAX],LOW[MAX],scc,clk,index,sk[MAX],vis[MAX],col[MAX],in[MAX],out[MAX]; 
void Tarjan(int x) {
	DFN[x] = LOW[x] = ++clk;
	vis[x]=1;
	sk[++index] = x;
	for(int i = head[x]; ~i; i = e[i].ne) {
		int v = e[i].to;
		if(DFN[v] == 0) {
			Tarjan(v);
			LOW[x] = min(LOW[x],LOW[v]);
		}
		else if(vis[v]) {
			LOW[x] = min(LOW[x],DFN[v]);
		}		
	}
	if(LOW[x] == DFN[x]) {
		scc++;
		while(1) {
			int tmp = sk[index];index--;
			vis[tmp]=0;
			col[tmp] = scc;
			if(tmp == x) break;
		}				
	}	
}
void init() {
	scc=clk=tot=TOT=index=0;
	for(int i = 1; i<=n; i++) {
		vv[i].clear();
		head[i] = HEAD[i] = -1;
		vis[i] = DFN[i] = LOW[i] = in[i] = out[i] = dp[i] = 0;
	}
	for(int i = 1; i<=n; i++) {
		for(int j = 1; j<=n; j++) ok[i][j]=0;
	}
}
int dfs(int cur){
	if(dp[cur])return dp[cur];
	int num=0;
	int up = vv[cur].size();
	for(int i = 0; i<up; i++) {
		int v = vv[cur][i];
		num=max(num,dfs(v));
	}
	return dp[cur]=num+1;
}
int main()
{
	int t;
	cin>>t;
	while(t--) {
		scanf("%d%d",&n,&m);		
		init();
		for(int a,b,i = 1; i<=m; i++) {
			scanf("%d%d",&a,&b);
			add(a,b);
		}
		for(int i = 1; i<=n; i++) {
			if(DFN[i] == 0) Tarjan(i);
		}
		for(int a,b,i = 1; i<=tot; i++) {
			a=col[e[i].fr],b=col[e[i].to];
			if(a==b) continue;
			if(ok[a][b]) continue;
			ok[a][b]=1;
			in[b]++;
			out[a]++;
			vv[a].pb(b);
		}
		int flag = 0;
		for(int i = 1; i<=n; i++){
			if(dfs(LOW[i]) == scc){flag=true;break;}//或者dfs(i)也可以ac
		}
		if(flag) puts("Yes");
		else puts("No");
	}
	return 0 ;
}

这里送上一种虽然错误但是可以AC的代码，引以为戒。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 1000 + 5;
struct Edge {
	int fr,to,ne;
} e[6005],E[6005];
int f[MAX];
int getf(int v) {
	return f[v] == v ? v : f[v] = getf(f[v]); 
}
void merge(int u,int v) {
	int t1 = getf(u),t2 = getf(v);
	f[t2] = t1;
}
int head[MAX],HEAD[MAX],tot,TOT;
bool ok[MAX][MAX];
void add(int u,int v) {
	e[++tot].to = v;
	e[tot].fr = u;
	e[tot].ne = head[u];
	head[u] = tot;
}
int n,m;
int DFN[MAX],LOW[MAX],scc,clk,index,sk[MAX],vis[MAX],col[MAX],in[MAX],out[MAX]; 
void Tarjan(int x) {
	DFN[x] = LOW[x] = ++clk;
	vis[x]=1;
	sk[++index] = x;
	for(int i = head[x]; ~i; i = e[i].ne) {
		int v = e[i].to;
		if(DFN[v] == 0) {
			Tarjan(v);
			LOW[x] = min(LOW[x],LOW[v]);
		}
		else if(vis[v]) {
			LOW[x] = min(LOW[x],DFN[v]);
		}		
	}
	if(LOW[x] == DFN[x]) {
		scc++;
		while(1) {
			int tmp = sk[index];index--;
			vis[tmp]=0;
			col[tmp] = scc;
			if(tmp == x) break;
		}				
	}	
}
void init() {
	scc=clk=tot=TOT=index=0;
	for(int i = 1; i<=n; i++) {
		head[i] = HEAD[i] = -1;
		f[i]=i;
		vis[i] = DFN[i] = LOW[i] = in[i] = out[i] = 0;
	}
	for(int i = 1; i<=n; i++) {
		for(int j = 1; j<=n; j++) ok[i][j]=0;
	}
}
int main()
{
	int t;
	cin>>t;
	while(t--) {
		scanf("%d%d",&n,&m);		
		init();
		for(int a,b,i = 1; i<=m; i++) {
			scanf("%d%d",&a,&b);
			add(a,b);
		}
		for(int i = 1; i<=n; i++) {
			if(DFN[i] == 0) Tarjan(i);
		}
		for(int a,b,i = 1; i<=tot; i++) {
			a=col[e[i].fr],b=col[e[i].to];
			if(a==b) continue;
			if(ok[a][b]) continue;
			ok[a][b]=1;
			merge(a,b);
			in[b]++;
			out[a]++;
		}
		int ans = 0;
		int flag = 0,ru=0,chu=0;
		for(int i = 1; i<=scc; i++) {
			if(f[i] == i) ans++;
			if(in[i]==out[i]) continue;
			if(in[i]-out[i]==1) ru++;
			else if(out[i]-in[i]==1) chu++;
			else {flag=1; break;}
		}	
		if(ans > 1 || flag == 1 || ru!=chu || ru>1 || chu>1  ) puts("No");
		else puts("Yes");
	}


	return 0 ;
}

但是其实这样是不对的：

1
3 3
3 1
1 2
3 2

这组样例就过不了，所以不能简单判断一个有向图欧拉通路。

【POJ - 2762】Going from u to v or from v to u?（Tarjan缩点，树形dp 或 拓扑排序，欧拉图相关）

【POJ - 2762】Going from u to v or from v to u?（Tarjan缩点，树形dp 或拓扑排序，欧拉图相关）