POI2008 Toll

POI
并查集, 拓扑排序

POI2008 Toll

题目大意：

城市中有n个镇子，m条双向边。每一条边连接两个不同的小镇，并且保证没有重复的路。你要把其中一些路变成单向边，使得每一个小镇有且只有一个入度。

( $n \le 10^5$ , $m \le 2 \times 10^5$ )

题解：

倘若题目改成每一个小镇只有一个出度，实际上是对题目没有什么影响的。（可以理解成把留下的单向边方向都换一下，这样就满足每一个小镇只有一个出度了。）

但这样我们就可以发现，每一个连通块，最后构造出来的图一定是一棵基环外向树。

于是，只要每一个连通块都存在一个环，就一定可以构造出解。

我们可以用并查集来找环，并留下需要的无向边。

之后，利用拓扑排序给留下的边定向。遇到环时，断开环上任意一点，绕一圈即可。

Code:

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
#include<queue>
#include<vector>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
const int N=100001;
int n,m;
struct Edge{
	int nxt[N<<2],to[N<<2],tot_edge,head[N];
	Edge(){
		memset(head,-1,sizeof(head));
	}
	void add_edge(int a,int b){
		to[tot_edge]=b;
		nxt[tot_edge]=head[a];
		head[a]=tot_edge++;
	}
}pre_edge,edge;
#define traverse(edge,i,x) for(int i=edge.head[x];~i;i=edge.nxt[i])
int tot_id;
bool vis[N];
int cnt[N],ans[N];
queue<int>Q;
vector<int>node[N];
void dfs(int p){
	vis[p]=true;node[tot_id].push_back(p);
	traverse(pre_edge,i,p){
		int to=pre_edge.to[i];
		if(!vis[to])dfs(to);
	}
}
int NO(){
	puts("NIE");
	return 0;
}
int YES(){
	puts("TAK");
	for(int i=1;i<=n;i++)
		printf("%d\n",ans[i]);
	return 0;
}
void solve(int p,int f){
	traverse(edge,i,p){
		int to=edge.to[i];
		if(to==f)continue;
		if(!ans[to]){
			ans[to]=p;
			return solve(to,p);
		}
	}
}
struct Union{
	int par[N];
	void init(){
		for(int i=1;i<=n;i++)par[i]=i;
	}
	int getpar(int p){
		if(par[p]!=p)par[p]=getpar(par[p]);
		return par[p];
	}
	void unite(int a,int b){
		a=getpar(a),b=getpar(b);
		par[a]=b;
	}
	bool is_same(int a,int b){
		a=getpar(a),b=getpar(b);
		return a==b;
	}
}U;
int main(){
	Rd(n),Rd(m);
	for(int i=1,a,b;i<=m;i++){
		Rd(a),Rd(b);
		pre_edge.add_edge(a,b);
		pre_edge.add_edge(b,a);
	}
	for(int i=1;i<=n;i++){
		if(!vis[i])dfs(i),tot_id++;
	}
	U.init();
	memset(vis,0,sizeof(vis));
	for(int i=0;i<tot_id;i++){
		bool flag=false;
		for(int j=0;j<node[i].size();j++){
			int p=node[i][j];
			if(vis[p])continue;
			vis[p]=true;
			traverse(pre_edge,k,p){
				int to=pre_edge.to[k];
				if(vis[to])continue;
				if(U.is_same(p,to)){
					if(!flag){
						flag=true;
						edge.add_edge(p,to);
						edge.add_edge(to,p);
						cnt[p]++,cnt[to]++;
					}
				}else{
					U.unite(p,to);
					edge.add_edge(p,to);
					edge.add_edge(to,p);
					cnt[p]++,cnt[to]++;
				}
			}
		}
		if(!flag)return NO();
	}
	for(int i=1;i<=n;i++){
		if(cnt[i]==1)Q.push(i);
	}
	while(!Q.empty()){
		int p=Q.front();Q.pop();
		traverse(edge,i,p){
			int to=edge.to[i];
			if(!ans[p]&&!ans[to]){
				ans[p]=to;
				if((--cnt[to])==1)Q.push(to);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(!ans[i])solve(i,0);
	}
	return YES();
}
分享到 评论