牛客练习赛25 定向(桥+tarjan)

题意


给一张无向图,你需要将边定向,使得定向后的有向图强连通。

思路


难点在于如何判断结果不存在。
依据连通分量的知识,可以得出结论:如果给定的无向图中存在桥的话,结果一定不存在,否则我们一定可以找出答案,且这个答案直接dfs即可。
如何判断是否有桥
这里因为是否有桥的判定为,子节点v low[v] > 父节点dfn[u]。
若不存在这样的点说明所有的子节点都存在返祖边指向其祖先,而因为我们是dfs,祖先又有边指向子节点,可想而知此时就是一个连通图.所以在从起始点dfs一下分边即可。(可知,答案不唯一)

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
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
int n,m,cnt,cont;
int dfn[maxn],low[maxn],head[maxn],fa[maxn],vis[maxn];
struct Edge
{
int to,nxt,dir,used;
}e[maxn << 2];
void init()
{
cnt = 0,cont = 1;
for(int i = 1;i <= n;++i)
{
head[i] = -1,vis[i] = 0,fa[i] = i;
}
}
void add(int a,int b)
{
e[cnt].to = b;
e[cnt].nxt = head[a];
e[cnt].used = 0;
head[a] = cnt++;
}
void tarjan(int cur,int par)
{
dfn[cur] = low[cur] = cont++;
fa[cur] = par;
for(int i = head[cur];~i;i = e[i].nxt)
{
int nxt = e[i].to;
if(!dfn[nxt])
{
tarjan(nxt,cur);
low[cur] = min(low[cur],low[nxt]);
}
else if (nxt != par){ //不通过父亲访问祖先
low[cur] = min(low[cur],dfn[nxt]);
}
}
return;
}
void dfs(int cur)
{
for(int i = head[cur];~i;i = e[i].nxt)
{
int nxt = e[i].to;
if(e[i].used) continue;
e[i].used = 1,e[i^1].used = 1; // i 和 i^1 是一对反向边
e[i].dir = 1,e[i^1].dir = 0;
if(vis[nxt]) continue;
vis[nxt] = 1;
dfs(nxt);
}
}
int main()
{
scanf("%d %d",&n,&m);
init();
for(int i = 0;i < m;++i)
{
int a,b;
scanf("%d %d",&a,&b);
add(a,b),add(b,a);
}
tarjan(1,1);
bool flag = true;
for(int i = 1;i <= n;++i)
{
int par = fa[i];
if(low[i] > dfn[par]) // 存在桥一定不可能
{
flag = false;
break;
}
}
if(!flag)
puts("impossible");
else
{
vis[1] = 1;
dfs(1);
for(int i = 0;i < cnt;i += 2)
printf("%d",e[i].dir);
puts("");
}
return 0;
}

-------------本文结束感谢您的阅读-------------

万水千山总是情,就给五毛行不行!

相关文章: