链接

欧拉回路板题

AC代码：

#include <bits/stdc++.h>
using namespace std; 

int n,G[151][151];
char x,y;
int cntIN[151];
bool ext[151];
int sum;
char cc[10000000];
int fir,len;

void dfs(int now)
{
    for (int i = 1; i <= 150; i++)
    {
        if(G[now][i] > 0)
        {
            G[now][i]--;
            G[i][now]--;
            dfs(i);
        }
    }
    cc[++len] = now;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x >> y;
        ext[x] = true,ext[y] = true;
        G[x][y]++,G[y][x]++;
        cntIN[x]++,cntIN[y]++;
    }
    for (int i = 1; i <= 150; i++)
    {
        if(ext[i] && (cntIN[i] & 1) == 1)
        {
            sum++;
            if(!fir)fir = i;
        }
    }
    if(sum && sum > 2)
    {
        cout << "No Solution";
        return 0;
    }
    dfs(fir);
    if(len < n + 1)
    {
        cout << "No Solution";
    }
    else
    {
        for (int i = len; i > 0; i--)
        {
            cout << cc[i];
        }
    }
    return 0;
}

错误示范：

​
#include <bits/stdc++.h>
using namespace std;

int n,cnt;
map <char,int> m;
int G[501][501];
int len = 0;
char x,y;
char lab[150];
int a,b;
int cntIN[150];
int fir,sum;
int cc[10000000];
bool flag;
int i,v,u;
struct node
{
    char na;
    int la;//原本的编号
}va[100];

void bfs()
{
    int i;
    while(1)
    {
        v = cc[len];
        flag = false;
        if(cntIN[v] == 3 && G[v][v] == 2)//下面的for走完，最后的自环就被孤立了，所以提前特判
        {
            G[v][v] = 0;
            cntIN[v] = 0;
            cc[++len] = v;
        }
        for (i = 1; i <= cnt; i++)
        {   
            //if( lab[v] == 'x' && va[i].la == 25)cout << "Ppppp"<< va[i].la << " ";

            if(G[v][ va[i].la ] > 0)
            {
                G[v][ va[i].la ]--;
                G[ va[i].la ][v]--;
                cntIN[v]--,cntIN[ va[i].la ]--;
                //if(va[ i ].na == 't')cout << "oooo" << lab[v] << "###";
                cc[++len] = va[ i ].la;
                flag = true;
                break;
            }
        }
        if(len == n + 1)
        {
            for (i = 1; i <= len; i++)
            {
                cout << lab[ cc[ i ] ];
            }
            break;
        }
        if(flag == false)
        {
            //无路可走
            if(len < n + 1)
            {
                cout << len;
                for (i = 1; i <= len; i++)
                {
                    cout << lab[ cc[ i ] ];
                }
            //cout << G[ m['x'] ][ m['x'] ] ;
                cout << "No Solution";//不连通
                break;
            }
        }
    }
}

bool cmp(node x,node y)
{
    return x.na < y.na;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x >> y;
        //if(x == 'x' && y == 'x')cout << "pppp";
        if(m[x] == 0)m[x] = ++cnt,lab[cnt] = x,va[cnt].na = x,va[cnt].la = cnt;
        if(m[y] == 0)m[y] = ++cnt,lab[cnt] = y,va[cnt].na = y,va[cnt].la = cnt;
        a = m[x],b = m[y];
        G[a][b]++;
        G[b][a]++;
        cntIN[a]++,cntIN[b]++;
        //if(G[ m['t'] ][ m['x'] ] == 1)cout << " ppp" << a << "pppp" << "b" << "pppp";
    }
    //cout << G[ m['x'] ][ m['x'] ] << " ";
    sort(va + 1, va + cnt + 1,cmp);
    //cout << G[ m['t'] ][ m['x'] ] << " ppppppp";
    for (int i = 1; i <= cnt; i++)
    {
        if(cntIN[ va[i].la ] % 2 == 1)
        {
            sum++;
            if(fir == 0)fir = i;
        }
    }
    if(sum > 2)cout << "No Solution";
    else
    {
        if(sum == 0)
        {
            fir = 1;
        }
        cc[++len] = va[ fir ].la;
        bfs();
    }
    return 0;
}

​

 错误原因：

        1.没考虑自环

        2.欧拉路径要先走欧拉回路，再走欧拉路径，否则走不完