void init()
{
memset(head,-1,sizeof(head));
tot=0;
memset(vis,0,sizeof(vis));
}
void add(inHale Waihona Puke x,int y)//有向图{
to[tot]=y,nxt[tot]=head[x],head[x]=tot++;
{
memset(head,-1,sizeof(head));
memset(d,0,sizeof(d));
memset(vis,0,sizeof(vis));
tot=0;
ans.clear();
}
void add(int x,int y,int z)//加双向边，如果是有向图则只加单向边
{
d[x]++,to[tot]=y,id[tot]=z,nxt[tot]=head[x],head[x]=tot++;
*/
const int N=10010;
const int M=100010;
//链式前向星
int head[N],to[M<<1],nxt[M<<1];
int tot;
int dfn[N],low[N],tm;
int belong[N];//每个点属于哪个边双
int bridge[M];//是否是桥
add(x,y,i);
}
int flag=0;//是否存在欧拉回路
for(int i=1; i<=n; i++)
if(d[i]&1) flag=1; //有奇数度的点，不存在欧拉回路
//如果是欧拉路径则修改相应判断条件
for(int i=1; i<=n; i++)
{
if(d[i]>0)//如果是欧拉路径，则从满足条件的起点开始dfs
for(int i=1; i<=n; i++)
if(!belong[i]) dfs(i,++num);
return 0;
}
3.点双连通分量
/*
求无向图的割点和每个点所属的点双连通分量，复杂度O(M)
无向图中去掉任意一个点不改变连通性称为点双联通
割点可能属于多个点双
在dfs树中，根节点多余1个儿子则为割点，其余点如果在不经过dfs到自己的那条树边的情况下，不能回到比自己高的点，则为割点
*/
const int N=10010;
const int M=100010;
//链式前向星
int head[N],to[M<<1],nxt[M<<1];
int tot;
int dfn[N],low[N],tm;
int S[N],top;//用栈存储dfs路径上的结点
int belong[N];//每个点属于哪个强连通分量
if(dfn[x]<=low[y])
{
if(fa||son>1) cut[x]=1;//x是多余一个儿子的根节点或回不到更高的点，则x是割点
num++;
belong[num].clear();
while(1)
{
cut[S[top]]=1;
belong[num].push_back(S[top]);
if(S[top--]==y) break;
dfs(to[i],y);
}
}
int n,m,x,y;
int main()
{
scanf("%d%d",&n,&m);
init();
for(int i=1; i<=m; i++)
{
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=1; i<=n; i++)
if(!dfn[i]) tarjan(i,-1);
add(x,y);
}
for(int i=1; i<=n; i++)
if(!dfn[i]) tarjan(i,0);
return 0;
}
4.强连通分量
/*
求有向图每个点所属的强连通分量，复杂度O(M)
有向图中任意两点都相互可达为强连通
在dfs树中，点如果在不经过dfs到自己的那条树边的情况下，恰好能回到自己，则为对应强连通分量的最高点，其余点保存在栈中
}
else if(low[x]>dfn[y]) low[x]=dfn[y];
}
if(dfn[x]==low[x])//x是强连通分量的最高点
{
num++;
while(1)
{
belong[S[top]]=num;
if(S[top--]==x) break;
}
}
}
int n,m,x,y;
int main()
{
dfn[x]=low[x]=++tm;
S[++top]=x;
for(int i=head[x]; i>=0; i=nxt[i])
{
int y=to[i];
if(y==fa) continue;
if(!dfn[y])
{
if(!fa) son++;
tarjan(y,x);
if(low[x]>low[y]) low[x]=low[y];//low记录能回到的最高点
1.欧拉回路
/*
判断是否存在欧拉回路，如果存在则打印回路，复杂度O(M)
无向连通图存在欧拉回路：每个点的度为偶数
无向连通图存在欧拉路径：两个点的度为奇数
有向连通图存在欧拉回路：每个点的入度等于出度
有向连通图存在欧拉路径：一个点入度等于出度+1，一个点出度等于入度+1，其余点入度等于出度
构造回路的方法：每次寻找一条简单回路，并将新回路插入到老回路中
for(int i=head[x]; i>=0; i=nxt[i])
{
if((i^1)==fa) continue;
if(!dfn[to[i]])
{
tarjan(to[i],i);
if(low[x]>low[to[i]]) low[x]=low[to[i]];//low记录能回到的最高点
}
else low[x]=min(low[x],dfn[to[i]]);
int num;//强连通个数
void init()
{
memset(head,-1,sizeof(head));
tot=0;
memset(dfn,0,sizeof(dfn));
tm=0;
num=0;
top=0;
}
void add(int x,int y)//有向图
{
to[tot]=y,nxt[tot]=head[x],head[x]=tot++;
num=0;
son=0;
top=0;
}
void add(int x,int y)//无向图
{
to[tot]=y,nxt[tot]=head[x],head[x]=tot++;
to[tot]=x,nxt[tot]=head[y],head[y]=tot++;
}
void tarjan(int x,int fa)//重边对点双没有影响，fa为父节点即可
}
belong[num].push_back(x);
}
}
else if(low[x]>dfn[y]) low[x]=dfn[y];
}
}
int n,m,x,y;
int main()
{
scanf("%d%d",&n,&m);
init();
for(int i=1; i<=m; i++)
{
scanf("%d%d",&x,&y);
{
dfs(i);
break;
}
}
for(int i=0; i<2*m; i++)
if(!vis[i]) flag=1;//有多个非孤立点的联通块，不存在欧拉回路
if(flag) printf("NO\n");
else
{
printf("YES\n");
for(int i=m-1; i>=0; i--) printf("%d%c",ans[i],i?' ':'\n');//ans按逆序存储
int num;//边双个数
void init()
{
memset(head,-1,sizeof(head));
tot=0;
memset(bridge,0,sizeof(bridge));
memset(belong,0,sizeof(belong));
tm=0;
num=0;
}
void add(int x,int y)//无向图
{
to[tot]=y,nxt[tot]=head[x],head[x]=tot++;
to[tot]=x,nxt[tot]=head[y],head[y]=tot++;
}
void tarjan(int x,int fa)//fa记录dfs到x的树边，用边而不用父节点是为了处理重边