Freuryアルゴリズムはオラパスを求めます.

Freuryアルゴリズムはオラパスを求めます.
リラに関する問題をいくつか並べてみます.
ハイブリッド道路 poj 1637、zju 1992、hdu 3472
1 HDU 3018 Ant Trip
2 POJ 1041 John's trip
3 POJ 1386 Play on Words
4 POJ 2230 Watch Cow
5 POJ 2513 Colored Sticks
6 POJ 2337 Catenyms
7 POJ 1392 Ourobooss Snake
8 HDU 2894 DeBruijin
郵便配達問題  poj 2040 poj 2404ハミルトン回路  poj 2439 poj 2288 poj 1392 hdu 2894 hdu
3018
1116
2894
1956
3472
欧拉回路のfleuryアルゴリズムを求めて、重辺を求めることができます.

#include
#include
#include
#include
#include
#include
using namespace std;

const int N = 1005;
int n, m, flag, top, sum, du[N], ans[5005], map[N][N];

void dfs(int x)
{
    ans[++top] = x;
    for(int i = 1; i <= n; i++)
    {
        if(map[x][i] >= 1)
        {
            map[x][i]--;
            map[i][x]--;
            dfs(i);
            break;
        }
    }
}

void fleury(int x)
{
    top = 1;
    ans[top] = x;
    while(top > 0)
    {
        int k = 0;
        for(int i = 1; i <= n; i++)//       
        {
            if(map[ans[top]][i] >= 1)//      ans[top]             
            {k = 1; break;}
        }
        if(k == 0)//  x           （     ），       
        {
            printf("%d ", ans[top]);
            top--;
        }
        else if(k == 1)//    ，  dfs        
        {
            top--;//     
            dfs(ans[top+1]);
        }
    }
}
int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        memset(du, 0, sizeof(du));
        memset(map, 0, sizeof(map));

        for(int i = 1; i <= m; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            map[x][y]++; //   ，             ，            
            map[y][x]++;
            du[x]++;
            du[y]++;
        }
        flag = 1; // flag     。               1   
        sum = 0;
        for(int i = 1; i <= n; i++)
        {
            if(du[i] % 2 == 1)
            {
                sum++;
                flag = i;//      ，        
            }
        }
        if(sum == 0 || sum == 2)
            fleury(flag);
    }
    return 0;
}