1.1 description

给定由 n 个点 m 条边组成的无向连通图，保证没有重边和自环。 你需要找出所有边，满足这些边恰好存在于一个简单环中。一个环被称为简单环，当且仅当 它包含的所有点都只在这个环中被经过了一次。 注意到这些边可能有很多条，你只需要输出他们编号的异或和即可。

1.2 input

第一行两个数 n, m。 接下来 m 行，每行两个数 ai , bi，表示第 i 条边连接了 ai , bi。

1.3 output

输出一个数，表示所有满足条件的边的编号的异或和。 n ，m≤ 106 开氧气1ac9re 不开7wa3tle 样例全过了不知道为什么

#include<bits/stdc++.h>
using namespace std;
struct Edge{
	int next,to,c,from;
}edge[2000005];
int fa[2000005],n,m,cnt=2,head[1000005],mark[1000005],vis[2000005],dep[1000005],d,ans;
int st[2000005],top;
map<int,bool> mp;
void add(int u,int v){
	edge[cnt].from=u;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
	cnt++;
}
int find(int k){
    if(fa[k]==k)return k;
    return fa[k]=find(fa[k]);
}
void merge(int u,int v){
	if(find(u)!=find(v))fa[find(u)]=fa[find(v)];
}
void dfs(int now){
	d++;
	if(mark[now]){
		for(int i=top;edge[st[i]].to!=now||i==top;i--){
			merge(st[i],st[top]);
			merge(st[i]^1,st[top]);
			edge[st[i]].c++;
			edge[st[i]^1].c++;
		}
		return;
	}
	mark[now]=1,dep[now]=d;
	for(int i=head[now];i;i=edge[i].next){
		if(!vis[i]&&dep[edge[i].to]<dep[now]){
			st[top+1]=i;
			top++;vis[i]=vis[i^1]=1;
			dfs(edge[i].to);
			top--;vis[i]=vis[i^1]=0;
		}
	}
	mark[now]=0;
}
int main(){
	cin>>n>>m;
	for(int i=2,u,v;i<=2*m;i+=2){
		cin>>u>>v;
		add(u,v);
		add(v,u);
		fa[i]=i;
		fa[i+1]=i;
	}
	dfs(1);
	for(int i=2;i<=2*m+1;i++){
		find(i);
		if(edge[i].c!=1)mp[fa[i]]=1;
	}
	for(int i=2;i<=2*m+1;i+=2){
		if(mp[i]!=1){
			ans^=(i/2);
		}
	}
	cout<<ans;
	return 0;
}