求满足题目要求的简单环，做出图中所有的点双，用vector存储点双中的边，如果该点双满足点数=边数，就是我们想要的，求边的异或和即可；如果该点双点数小于边数，说明有不只一个环覆盖，不满足题意。
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define int long long
4 #define N 1000005
5 int read(){
6 int x=0,f=1;char ch;
7 while(ch>'9'||ch<'0'){
8 if(ch=='-') f=-1;ch=getchar();
9 }
10 while(ch>='0'&&ch<='9'){
11 x=x*10+ch-'0';ch=getchar();
12 }
13 return f*x;
14 }
15 int dfn[N],low[N],v[N],e[N],top1,top2;
16 int bcc,sc[N],n,m,x,y,ans;
17 int head[N],nxt[N*2],to[N*2],tot=1,num;
18 bool used[N],vis[N];
19 vector<int>a[N];//存点双连通分量含的边
20 void add(int x,int y){
21 nxt[++tot]=head[x];
22 head[x]=tot;
23 to[tot]=y;
24 }
25
26 void tarjan(int x){
27 dfn[x]=low[x]=++num;
28 v[++top1]=x;//存点
29 for(int i=head[x];i;i=nxt[i]){
30 int y=to[i];
31 if(used[i>>1]) continue;
32 used[i>>1]=1;
33 e[++top2]=i>>1;//存边
34 if(!dfn[y]){
35 tarjan(y);
36 low[x]=min(low[x],low[y]);
37 if(low[y]<dfn[x]) continue;//不是点双连通分量，跳过
38 bcc++;
39 while(1){
40 int z=v[top1--];
41 sc[bcc]++;
42 if(z==y) break;
43 }
44 sc[bcc]++;//割点也要加进去
45 while(1){
46 int z=e[top2--];
47 a[bcc].push_back(z);
48 if(z==(i>>1)) break;
49 }
50 }
51 low[x]=min(low[x],dfn[y]);
52 }
53 }
54
55 signed main(){
56 n=read(),m=read();
57 for(int i=1;i<=m;i++){
58 x=read(),y=read();
59 add(x,y),add(y,x);
60 }
61 tarjan(1);
62 for(int i=1;i<=bcc;i++){
63 if(a[i].size()!=sc[i]) continue;
64 for(int j=0;j<a[i].size();j++) vis[a[i][j]]=1;
65 }
66 for(int i=1;i<=m;i++) if(vis[i]) ans^=i;
67 printf("%d\n",ans);
68 }
用low[y]<dfn[x]判断其不是点双；注意tot从1开始；统计每个点双中点的数量时要加上割点（即数量要加1）
