（2022杭电多校六）1010-Planar graph（最小生成树）

题目：

 题意：给n个点和m条边，m条边将一个图分成若干个连通区域，然后我们可以删除一些边，问至少删除多少条边才能使得所有的区域是连通的，在所有的删边情况中选择字典序最小的一种情况进行输出。

先来思考一下，什么情况下才能使得所有区域是连通的？其实画个图观察不难发现，只有当图中没有环时整个区域才是连通的，现在问题就转化为我们至少删除多少条边才能使得图中没有环，由于树是一个没有环的最大连通子图，所以显然是将图删边使其形成一棵树，这样的话删除的边数一定是最小的，由于题目中要求删除的边的字典序最小，那么我们就可以考虑从编号大的边开始添加边，只要加进去该边不成环就把该边加入图中，这样最后没有加入图中的边就是我们要删除的边，那么我们直接按照字典序进行从小到大输出即可，这个过程就是利用类似kruscal的过程进行实现，只是我们不是按照边权进行排序，而是按照编号进行排序。

下面是代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<cmath>
using namespace std;
const int N=2e6+10;
int fu[N],u[N],v[N];
int find(int x)
{
	if(x!=fu[x]) fu[x]=find(fu[x]);
	return fu[x];
}
stack<int>st;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) fu[i]=i;
		for(int i=1;i<=m;i++)
			scanf("%d%d",&u[i],&v[i]);
		for(int i=m;i>=1;i--)
		{
			int fx=find(u[i]),fy=find(v[i]);
			if(fx==fy)
				st.push(i);
			else 
				fu[fx]=fy;
		}
		printf("%d\n",st.size());
		while(!st.empty())
		{
			printf("%d ",st.top());
			st.pop();
		}
		puts("");
	}
	return 0;
}