[筆記] Codeforces 920E: Connected Components?

[題意] 給一個有 n 個點的 undirected simple graph，並且告訴你這個 graph 中有 m 條邊被拿掉了，問有幾個 connected components？並且把 connected component 的大小由小到大印出來。
解法很單純，利用 BFS 或 DFS 就可以了，唯獨有一點要特別注意：因為 n 很大 (200,000)所從要維護一條序列，裡面存的是有哪些點還沒被拜訪過，這樣每次從一個點要開始拜訪其他點時只要找還在那條序列中的點就好。


實作如下：

	/*
	* =====================================================================================
	*
	* Filename: 920E.cpp
	*
	* Description: codeforces 920E: Connected Components?
	*
	* Version: 1.0
	* Created: 2018/02/08 (yyyy/mm/dd)
	* Revision: none
	* Compiler: g++14
	*
	* Author: lionking
	* Organization: None
	*
	* =====================================================================================
	*/
	#include <cstdio>
	#include <vector>
	#include <queue>
	#include <algorithm>
	#include <unordered_set>
	constexpr size_t MAX_VAL = 200000;
	template <typename T>
	using uset = std::unordered_set<T>;
	void findCC(const int N, const std::vector< uset<int> >& rm_edge)
	{
	std::vector<size_t> result;
	uset<int> remain(N + 1); // remaining un-visited vertices
	for (int i = 1; i <= N; ++i) { remain.emplace(i); }
	while (remain.empty() == false) {
	size_t count = 1;
	auto node = *(remain.begin());
	remain.erase(node);
	std::queue<int> q;
	q.push(node);
	while (q.empty() == false) {
	node = q.front(); q.pop();
	auto iter = remain.begin();
	while (iter != remain.end()) {
	const auto next = *iter;
	if (rm_edge[node].find(next) != rm_edge[node].cend()) {
	++iter;
	}
	else {
	q.push(next);
	count++;
	iter = remain.erase(iter);
	}
	}
	}
	result.push_back(count);
	}
	sort(result.begin(), result.end());
	printf("%lu\n", result.size());
	for (const auto& v : result) { printf("%lu ", v); }
	putchar('\n');
	}
	int main()
	{
	int n, m;
	while (scanf("%d %d", &n, &m) == 2) {
	std::vector< uset<int> > rm_edge(n + 1);
	for (int i = 0; i < m; ++i) {
	int x, y;
	if (scanf("%d %d", &x, &y) == 2) {
	rm_edge[x].emplace(y);
	rm_edge[y].emplace(x);
	}
	}
	findCC(n, rm_edge);
	}
	return 0;
	}

view raw codeforces-920E.cpp hosted with ❤ by GitHub