dfs找欧拉回路模板

dfs找欧拉回路
dfs找欧拉回路

#include
using namespace std;
const int N=2e5+10,M=2e5+10;
int h[N],e[M*2],ne[M*2],idx;
int n,m;
int t;
int dout[N];
int din[N];
bool vis[M*2];
int p[M*2];
int cnt=0;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}


void dfs(int u)
{
    for(int &i=h[u];i;i=ne[i])
    {
        if(vis[i]) continue;
        vis[i]=true;  
        if(t==1) vis[i^1]=true;
        int no;
         if(t==1)
        {
            if((i&1))
            {
              no=-(i/2);
            }else no=i/2;
        }else
        {
            no=i-1;
        }
       int j=e[i];
        dfs(j);
       p[++cnt]=no;
    }
}



int main()
{
    scanf("%d",&t);
    scanf("%d%d",&n,&m);
    idx=2;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        dout[a]++;
        din[b]++;
        if(t==1) add(b,a);
    }
    if(t==1)
    {
        for(int i=1;i<=n;i++)
        {
            if((din[i]+dout[i])%2!=0)
            {
                cout<<"NO"<<endl;
                return 0;
            }
        }
    }else
    {
        for(int i=1;i<=n;i++)
        {
            if(din[i]!=dout[i])
            {
                cout<<"NO"<<endl;
                return 0;
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(h[i])
        {
            dfs(i);
            break;
        }
    }
    if(cnt!=m)
    {
        cout<<"NO"<<endl;
        return 0;
    }
    cout<<"YES"<<endl;
    for(int i=cnt;i>=1;i--)
    {
        cout<<p[i]<<' ';
    }
    cout<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

求逆字典序最小的欧拉路径

#include
using namespace std;
const int N=510,M=2000;
int g[N][N];
int m;
int d[N];
int ans[M];
int cnt;

void dfs(int u)
{
    for(int i=1;i<=500;i++)
    {
        if(g[u][i])
        {
            g[u][i]--,g[i][u]--;
            dfs(i);
        
        }
    }    ans[++cnt]=u;
}


int main()
{
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        g[a][b]++;
        g[b][a]++;
        d[a]++;
        d[b]++;
    }
    int start=1;
    for(int i=1;i<=500;i++)
    {
        if(d[i]%2)
        {
        start=i;
            break;
        }
    }
    dfs(start);
    for(int i=cnt;i;i--)
    {
        printf("%d\n",ans[i]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

求字典序最小的以点表示的欧拉路径

#include 
using namespace std;
#define x first
#define y second
# define rep(i,be,en) for(int i=be;i<=en;i++)
# define pre(i,be,en) for(int i=be;i>=en;i--)
#define ll long long
#define endl "\n"
#define LOCAL
#define pb push_back
typedef pair<ll, ll> PII;
#define eb emplace_back
#define sp(i) setprecision(i)
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int din[N];
int dout[N];
vector<int>g[N];
int n,m;
int ans[N*2];
int del[N];
int cnt=0;
stack<int>s;

void dfs(int u)
{
   
    for(int i=del[u];i<g[u].size();i=del[u])
    {
        del[u]=i+1;
        dfs(g[u][i]);
    }
    //s.push(u);
     ans[++cnt]=u;
}


void solve()
{
    scanf("%d%d",&n,&m);
  
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        g[a].push_back(b);
        din[b]++;
        dout[a]++;
    }
    for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());
    int start=1;
    int f1=0;
    int f2=0;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(dout[i]!=din[i])
        {
            sum++;
            if(dout[i]==din[i]+1)
            {
                f2++;
            }else if(dout[i]+1==din[i])
            {
                f1++;
            }
        }
    }
    if(!(sum==0||(sum==2&&f1==1&&f2==1)))
    {
        printf("No\n");
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(din[i]+1==dout[i])
        {
            start=i;
            break;
        }
    }  
    dfs(start);

    for(int i=cnt;i>=1;i--)
    {
        printf("%d ",ans[i]);
    }
    // while(s.size()) 
    // {
    //     cout<
    //     s.pop();
    // }
    puts("");
}



signed main() {
// std::ios::sync_with_stdio(false);
//     std::cin.tie(nullptr);
    //#ifdef LOCAL
    //freopen("data.in.txt","r",stdin);
    //freopen("data.out.txt","w",stdout);
    //#endif
    int __ = 1;
    //cin>>__;
    while (__--)
        {
            solve();
        }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112