MnZn求助

#include<bits/stdc++.h>
#define ll long long
#define ls pos<<1
#define rs pos<<1|1
//#define DEBUG   
using namespace std;
const ll N = 2e5 + 10 ;
ll n,m; // n为边数 m为点数 
ll h[N],ne[N],ver[N],E[N],idx;
ll ans;
ll fa[N];
vector<ll> path;
bool used[N],cow[N];//used_i即麦片i是否被吃 cow_i即奶牛i顺序已定
struct node
{
	ll u,v; 
}edge[N];
ll find(ll x)//方便找环
{
	if( fa[x] == x ) return fa[x] ;
	return fa[x] = find( fa[x] ) ;
}
void link(ll u,ll v,ll w)
{
	E[idx] = w ;
	ver[idx] = v  ;
	ne[idx] = h[u];
	h[u] = idx ++ ;
}
// 搜索树上一定有解 
void dfs(ll x,ll fa) //方案按dfs序即可
{
	for(ll i=h[x];~i;i=ne[i])
	{
		ll y=ver[i];
		if( y == fa || used[y] ) continue ;
		ans++;
		path.push_back(E[i]);
		cow[E[i]]=1;
		used[y]=1;
		dfs(y,x);
	}
}
int main()
{  
	memset(h,-1,sizeof h);
	scanf("%lld%lld",&n,&m); 
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&edge[i].u,&edge[i].v);
	for(int i=1;i<=m;i++) fa[i] = i ; 
	for(int i=1;i<=n;i++)
	{
		ll u=find(edge[i].u),v=find(edge[i].v) ; 
		if( u != v ) // 某棵生成树 或 树与树之间 
		{
			if( !used[edge[i].u] && !used[edge[i].v] ) // 一定还是树 
			{
				link(u,v,i); //以编号为边权
				link(v,u,i);
				fa[u]=v;				
			}
			else if( used[edge[i].u] && used[edge[i].v] ) path.push_back(i); // 在两棵吃完的搜索树上 
			else // 某棵树挂到一棵吃过的树上 
			{
				ans++;
				path.push_back(i); cow[i]=1;
				if( used[edge[i].u] ) dfs(edge[i].v,edge[i].v),used[edge[i].v]=1 ;
				else dfs(edge[i].u,edge[i].u),used[edge[i].u]=1 ;
			}
		}
		else // 出现非树边 
		{
			if( used[edge[i].u] && used[edge[i].v] ) { cow[i]=1; path.push_back(i); continue; }  // 没得吃  
			//否则一定在一棵完整的搜索树上  
			ans++;
			used[edge[i].u] = 1  ; path.push_back(i); cow[i]=1; // 环边必须吃 
			dfs( edge[i].u, edge[i].u ); // 以被吃掉的节点为根开始dfs 	      
		}
	}
	for(int i=1;i<=n;i++) 
	{
		if(!cow[i]) //独立的搜索树
		{
			ans++;
			path.push_back(i);
			used[edge[i].u] = used[edge[i].v] = 1 ;	
			dfs(edge[i].u,edge[i].u);
			dfs(edge[i].v,edge[i].v);
		} 
	}
	printf("%lld\n",n-ans);
	for(auto x:path) printf("%lld\n",x); 
	return 0 ;
}