M题-暂时没想法

https://ac.nowcoder.com/acm/contest/79000/M

————————

做本题你需要会dfs或者并查集。本题解使用的是并查集。

目录

• 读题
• 思路
• 官方题解
• 参考代码片

读题：

题目中有重要信息，比如初始图肯定是两个“集合”以上。 （集合指的是两组城市，这两组间不存在通路）

然后是要重新建图，并且不能用原来的的路。

思路

如图：

（题目给的是上面那一行，我们的最终输出结果是下面的一行。

有大佬提示我了，我们最后的结果其实就是一颗树，所以ans大小就是n-1）

官方题解

参考代码片：

void solve()
{
	int n, m;
	cin >> n >> m;
	init(n);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		join(a, b);
	}
	vector<int>group;//每组的头
	map<int, int>h;//头是第几个数组
	vector<vector<int>>members;//每组的成员
	for (int i = 1; i <= n; i++)
	{
		if (!h.count(find(i)))
		{
			h[find(i)] = group.size();
			group.push_back(i);
			members.push_back(vector<int>());
			members[h[find(i)]].push_back(i);
		}
		else
		{
			int tou = find(i);
			members[h[tou]].push_back(i);
		}
	}

	cout << "Yes" << endl;
	int ans = n-1;
// 	for (int i = 0; i < members.size(); i++)
// 	{
// 		if (i == members.size() - 1)
// 		{
// 			ans += members[0].size() - 1;
// 		}
// 		else
// 		{
// 			ans += members[i + 1].size();
// 		}
// 	}
	cout << ans << endl;
	for (int i = 0; i < members.size(); i++)
	{
		if (i == members.size() - 1)
		{
			for (auto x : members[0])
			{
				if(x!=group[0])
				cout << group[i] << " " << x << endl;
			}
		}
		else
		{
			for (auto x : members[i + 1])
			{
				cout << group[i] << " " << x << endl;
			}
		}
	}
}