【洛谷 P8655】[蓝桥杯 2017 国 B] 发现环题解（邻接表+并查集+路径压缩）

[蓝桥杯 2017 国 B] 发现环

题目描述

小明的实验室有 $N$ 台电脑，编号 $\sim N$ 。原本这 $N$ 台电脑之间有 $N - 1$ 条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。

不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了 BUG。

为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？

输入格式

第一行包含一个整数 $N$ 。

以下 $N$ 行每行两个整数 $a$ 和 $b$ ，表示 $a$ 和 $b$ 之间有一条数据链接相连。

输入保证合法。

输出格式

按从小到大的顺序输出在环路上的电脑的编号，中间由一个空格分隔。

样例 #1

样例输入 #1

样例输出 #1

1 2 3 5

提示

对于 $30\%$ 的数据， $\le N \le 1000$ 。

对于 $100\%$ 的数据， $\le N \le 10^5$ ， $\le a,b \le N$ 。

时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛

思路

首先，从输入中读取电脑的数量 $N$ 。接着，进行并查集的初始化，使得每个电脑都是其自身的根节点，这是通过 init() 函数实现的。

然后进入一个循环，循环次数为电脑的数量，即 $N$ 次。在每次循环中，分别读取两个电脑的编号 $u$ 和 $v$ 。这两个编号表示电脑 $u$ 和 $v$ 之间有一条数据链接。

对于每一对电脑 $u$ 和 $v$ ，首先检查它们是否在同一个集合中。这是通过 check(u, v) 实现的，如果它们的根节点相同，返回 1；否则，返回 0。

如果 check(u, v) 返回 0，说明电脑 $u$ 和 $v$ 之间还没有路径，可以添加一条连接。此时，通过 merge(u, v) 将它们合并到同一个集合中，这是通过找到它们的根节点，然后将一个的根节点的父节点设置为另一个的根节点实现的。同时，通过 add(u, v) 在图中添加一条连接，这是通过在邻接表中分别为 $u$ 和 $v$ 添加对方的编号实现的。

如果 check(u, v) 返回 1，说明电脑 $u$ 和 $v$ 已经通过其他路径连接，再添加一条连接就会形成环。此时，需要找出环中的所有电脑。首先，重置 bitset<N> vis，这是一个位集，用于标记电脑是否被访问过。然后，设置环的目标节点 dest = v，这是因为电脑 $v$ 是形成环的那一条边的一个节点。最后，从电脑 $u$ 开始进行深度优先搜索（DFS），找出所有在环中的电脑。这是通过 dfs(u, 0) 实现的，其中 0 是电脑 $u$ 的父节点编号，因为 $u$ 是DFS的起点，所以其父节点编号为 0。

在深度优先搜索的过程中，首先标记当前电脑已被访问，这是通过 vis[x] = 1 实现的。然后，检查当前电脑是否是环的目标电脑，如果是，打印出所有已被访问的电脑（也就是环中的电脑），然后返回。如果不是，对当前电脑的所有邻居进行深度优先搜索，这是通过递归调用 dfs(i, x) 实现的，其中 i 是邻居的编号，x 是当前电脑的编号。最后，在DFS返回前，将当前电脑标记为未被访问，这是通过 vis[x] = 0 实现的。

AC代码

#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <stack>
#include <vector>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;

const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;

int n;
int pre[N];
vector<int> g[N];
stack<int> stk;
bitset<N> vis;
int dest;

int root(int a) {
	int i = a;
	while (i != pre[i]) {
		i = pre[i];
	}
	return (pre[a] = i);
}

void merge(int a, int b) {
	int ra, rb;
	ra = root(a);
	rb = root(b);
	if (ra == rb) {
		return;
	}
	pre[ra] = rb;
}

bool check(int a, int b) {
	int ra, rb;
	ra = root(a);
	rb = root(b);
	if (ra == rb) {
		return 1;
	}
	return 0;
}

void add(int u, int v) {
	g[u].push_back(v);
	g[v].push_back(u);
}

void init() {
	for (int i = 1; i <= n; i++) {
		pre[i] = i;
	}
}

void dfs(int x, int fa) {
	// cout << x << endl;
	vis[x] = 1;
	if (x == dest) {
		for (int i = 1; i <= n; i++) {
			if (vis[i]) {
				cout << i << " ";
			}
		}
		cout << "\n";
		return;
	}
	for (const auto i : g[x]) {
		if (i == fa) {
			continue;
		}
		dfs(i, x);
	}
	vis[x] = 0;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	init();
	for (int i = 1; i <= n; i++) {
		int u, v;
		cin >> u >> v;
		if (check(u, v)) {
			vis.reset();
			dest = v;
			dfs(u, 0);
		} else {
			merge(u, v);
			add(u, v);
		}
	}
	return 0;
}