【数据结构】欧拉回路（优化最短路-图论）

题面

题意

有一天一位灵魂画师画了一张图，现在要你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。

一共两个子任务：

1. 这张图是无向图。50（ 分）
2. 这张图是有向图。50（ 分）

输入格式

第一行一个整数 t，表示子任务编号。t∈{1,2}，如果 t=1 则表示处理无向图的情况，如果 t=2 则表示处理有向图的情况。

第二行两个整数 n,m，表示图的结点数和边数。

接下来 m 行中，第 i 行两个整数 vi，ui，表示第 i 条边（从 1 开始编号），保证 1 ≤ vi，ui ≤ n。

如果 t=1 则表示 vi 到 ui 有一条无向边。

如果 t=2 则表示 vi 到 ui 有一条有向边。

图中可能有重边也可能有自环。

输出格式

如果不可以一笔画，输出一行 “NO”。

否则，输出一行 “YES”，接下来一行输出一组方案。

如果 t=1，输出 m 个整数 p1,p2,…,pm。令 e=∣pi∣，那么 e 表示经过的第 i 条边的编号。如果 pi 为正数表示从 ve 走到 ue，否则表示从 ue 走到 ve。
如果 t=2，输出 m 个整数 p1,p2,…,pm。其中 pi 表示经过的第 i 条边的编号。

样例数据

【样例输入1】
1
3 3
1 2
2 3
1 3
【样例输出1】
YES
1 2 -3
 
 
【样例输入2】
2
5 6
2 3
2 5
3 4
1 2
4 2
5 1
【样例输出】
YES
4 1 3 5 2 6

思路

• 欧拉回路的模板，但只能算一个环，图原本可能不连通。 另外会有很多自环，也要优化一下，否则会超时。
• 有向图的欧拉回路就是入度与出度之和一定是一个偶数（如果入度为1，出度为-1，和为0），无向图的点度一定是偶数，用这个来判断是否为欧拉回路。

代码（70分）

应该是没有优化很多自环的情况

#include <bits/stdc++.h>
#define ll long long 
#include <vector>
#include <stack>
#define db double 
#define ls p<<1 
#define rs p<<1|1
using namespace std;
const int N=100010, M=1000010;
 
inline ll read() {
    char c=getchar(); int x=0,f=1;
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
    return x*f;
}
 
bool flag[M];
ll in[N], out[N], f[M];
int head[N], ver[M] ,nxt[M];
ll type, n, m, tot=1, x, y;
 
vector<ll> ans;
 
void add(int u,int v) {
    ver[++tot]=v;
    nxt[tot]=head[u];
    head[u]=tot;
}
 
struct ed {
    int to,nxt;
}t[10010<<1];
 
void dfsearch(int x) {
    for(int &i=head[x],y; y=ver[i],i; i=nxt[i]) {
        ll c=(type==1?i/2:i-1);
        ll sig = i%2;
        if(flag[c]) continue;
        flag[c]=1;
        dfsearch(y);
        if(type==1) 
			ans.push_back(sig?-c:c);
        else 
			ans.push_back(c);
    }
}
 
int main () {
	type = read();
	n = read();
	m = read();
    for(int i=1; i<=m; i++) {
    	x = read();
    	y = read();
        add(x,y);
        if(type==1) add(y,x);
        out[x]++;  in[y]++;
    }
    
    if(type==1) {
        for(int i=1; i<=n; i++)
            if((in[i]+out[i])%2) {
			printf("NO\n");  
			return 0;
		} 
	} 
    
	else {
		for(int i=1; i<=n; i++) 
            if(in[i]!=out[i]) {
				printf("NO\n");  
				return 0;
			} 
	}
        
    for(int i=1; i<=n; i++)
        if(head[i]) {
			dfsearch(i); 
			break;
		}
        
    if(ans.size()!=m) {
		cout << "NO" << endl; 
		return 0;
	}
    
    cout<<"YES"<<endl;
    if(type==1) 
		for(int i=0; i<=m-1; i++) 
			printf("%lld ", -1*ans[i]);
    if(type==2) 
		for(int i=m-1; i>=0; i--) 
			printf("%lld ", ans[i]);
    puts("");
    return 0;
}

AC_Code

#pragma comment(linker, "/STACK:102400000,102400000")//手动开大栈区
#include<bits/stdc++.h>
using namespace std;  
int const N=4e5+10;  
int n,m,cnt,h[N],st[N<<1],top,in[N],out[N],vis[N<<1],f[N],us[N<<1],num[N];  
vector<int> a[N],c[N],b[N];  
void dfs(int x,int lm){
	while (b[x].size()){
		int y=b[x][b[x].size()-1];  
		int t=c[x][b[x].size()-1];  
		b[x].pop_back();  
		c[x].pop_back();   
		if(y<lm) continue;  
		if(!vis[abs(y)]){
			vis[abs(y)]=1;  
			dfs(t,lm);  
			st[++top]=y; 
		}			
	} 
}  
int find(int x){
	return x==f[x]? x:f[x]=find(f[x]); 
}
int main(){
	int t;
	scanf("%d",&t);  
	cnt=top=0;  
	memset(h,0,sizeof(h));  
	memset(vis,0,sizeof(vis)); 
	memset(in,0,sizeof(in)); 
	memset(out,0,sizeof(out));  
	for(int i=1;i<=n;i++) 
		a[i].clear(); 
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) f[i]=i; 
	for(int i=1;i<=m;i++){
		int x,y; 
		scanf("%d%d",&x,&y);  
		c[x].push_back(y);  
		c[y].push_back(x); 
		b[x].push_back(i);  
		b[y].push_back(-i); 
		f[find(x)]=find(y);  
	}  
	for(int i=1;i<=n;i++)  
		a[find(i)].push_back(i); 
	int check=0,ot=0; 
	for(int i=1;i<=n;i++) 
	{
		if(a[i].size()==0) continue;   
		int num=0,nd,sum=0;   
		for(int j=0;j<a[i].size();j++){
			int x=a[i][j]; 
			nd=x;  	
			sum+=b[x].size();  
			for(int k=0;k<c[x].size();k++){
				int v=c[x][k];  
				int c=abs(b[x][k]);  
				if(t==2 && b[x][k]<0) continue;  
				if(us[c]) continue; 
				us[c]=1;  
				if(t==1) in[x]++,in[v]++;  
				else out[x]++,in[v]++;  
			}
		}
		for(int j=0;j<a[i].size();j++){
			int x=a[i][j];  
			if(t==1){
				if(in[x]%2==1) 
					num++; 
			}else {
				if(in[x]!=out[x])
					num++;  
			}
		}
		if(t==1){
			if(num==0)
			{	
				if(sum)
					dfs(nd,-10000000),ot++;  
			}
			else check=1;   	
		}else {
			if(num==0)
			{	
				if(sum)
					dfs(nd,0),ot++;  
			}
			else check=1;  
		}
	}
	if(check || ot>1) printf("NO\n");  
	else {
		printf("YES\n");  
		for(int i=top;i>=1;i--)  printf("%d ",st[i]);  
	}
	return 0; 
}