POJ 3694 Network【LCA + 并查集】

ACM_图论

题目链接：

http://poj.org/problem?id=3694

题意：

给定无向图，给定若干询问，每个询问加入一条边，问加入该边后图中桥的数目。

分析：

首先想是缩点，缩点之后形成的是棵树，树边均为桥，每加一条新边，就把他们所在集合并起来。这样就在树上形成了一个环，环中所有边都不再是桥。找环中的边的过程实际就是找最近公共祖先的过程，向上爬的过程中遇到的所有边都不再是桥。
集合并起来很自然的想到用并查集搞，而缩点过程我们也可以在tarjan求桥的同时求用并查集搞。对于每个询问在两个点向上爬的时候判断该点是否与父节点在同一集合中，若不是，说明连边为桥，删去，并将该点与其父节点并起来。
QAQ在缩点的时候我们用深度最低的点来代表他所处在的强连通分量中，利用这点就可以在求LCA时集合合并的同时让结点向上一步一步的跳。

代码：

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
/*************************************************************************
    > File Name: 3694.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/9/14 13:37:27
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5, maxm = 2e5 + 5;
int head[maxn], dfn[maxn], low[maxn];
struct EDGE{
	int to, next;
	bool vis;
};
EDGE edge[maxm * 2];
int tot, dfnum;
int btot;
int pa[maxn], fa[maxn];
int dep[maxn];
void init(int n)
{
    tot = 0;
	btot = 0;
    dfnum = 1;
    memset(head, -1, sizeof(head));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
	for(int i = 1; i <= n; i++) pa[i] = i;
}
int _find(int x)
{
	if(x == pa[x]) return x;
	return pa[x] = _find(pa[x]);
}
void unit(int x, int y)
{
	int rx = _find(x), ry = _find(y);
	if(rx == ry) return;
	pa[rx] = ry;
}
void addedge(int u, int v)
{
	edge[tot].vis = false;
	edge[tot].to = v;
	edge[tot].next = head[u];
	head[u] = tot++;
}
void dfs(int u, int depth)
{
    dfn[u] = low[u] = dfnum++;
	dep[u] = depth;
    for(int i = head[u]; i != -1; i = edge[i].next){
        if(edge[i].vis) continue;
		edge[i].vis = edge[i ^ 1].vis = true;
		int v = edge[i].to;
        if(!dfn[v]){
			fa[v] = u;
            dfs(v, depth + 1);
            low[u] = min(low[u], low[v]);
		}else low[u] = min(low[u], dfn[v]);
        if(low[v] <= dfn[u]) unit(v, u);
		else btot++;
    }
}
int LCA(int u, int v)
{
	int cnt = 0;
	while(dep[u] > dep[v]){
		if(_find(u) != _find(fa[u])) cnt++;
		unit(u, fa[u]);
		u = fa[u];
	}
	while(dep[v] > dep[u]){
		if(_find(v) != _find(fa[v])) cnt++;
		unit(v, fa[v]);
		v = fa[v];
	}
	while(u != v){
		if(_find(u) != _find(fa[u])) cnt++;
		unit(u, fa[u]);
		if(_find(v) != _find(fa[v])) cnt++;
		unit(v, fa[v]);
		u = fa[u];
		v = fa[v];
	}
	return cnt;
}
int main (void)
{
	int n, m;
	int a, b;
	int kas = 1;
	while(~scanf("%d%d", &n, &m) && (n + m)){
		init(n);
		for(int i = 0; i < m; i++){
			scanf("%d%d", &a, &b);
			addedge(a, b);
			addedge(b, a);
		}
		fa[1] = 1;
		dfs(1, 1);
		int q;scanf("%d", &q);
		printf("Case %d:\n", kas++);
		for(int i = 0; i < q; i++){
			scanf("%d%d", &a, &b);
			if(_find(a) != _find(b)) btot -= LCA(a, b);
			printf("%d\n", btot);
		}
		puts("");
	}
	return 0;
}
文章目录
  1. 1. 题目链接：
  2. 2. 题意：
  3. 3. 分析：
  4. 4. 代码：