.Re: 欧拉回路 - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: kaman (天外飞仙), 信区: ACMICPC
标  题: Re: 欧拉回路
发信站: 荔园晨风BBS站 (Sat Sep  4 22:46:30 2004), 站内信件

标程：

#include <stdio.h>
#include <string.h>

#define MAXI 500
#define MAXF 1200
char conn[MAXI][MAXI];
int deg[MAXI];
int nconn;

int path[MAXF];
int plen;

/* this is exactly the Eulerian Path algorithm */
void find_path(int loc)
{
  int lv;

  for (lv = 0; lv < nconn; lv++)
    if (conn[loc][lv])
     {
      /* delete edge */
      conn[loc][lv]--;
      conn[lv][loc]--;
      deg[lv]--;
      deg[loc]--;

      /* find path from new location */
      find_path(lv);
     }

  /* add this node to the `end' of the path */
  path[plen++] = loc;
}

int main()
{
  FILE *fin, *fout;
  int nfen;
  int lv;
  int x, y;

  scanf ("%d", &nfen);
  for (lv = 0; lv < nfen; lv++)
   {
    scanf ("%d %d", &x, &y);
    x--; y--;
    conn[x][y]++;
    conn[y][x]++;
    deg[x]++;
    deg[y]++;
    if (x >= nconn) nconn = x+1;
    if (y >= nconn) nconn = y+1;
   }

  /* find first node of odd degree */
  for (lv = 0; lv < nconn; lv++)
    if (deg[lv] % 2 == 1) break;
  /* if no odd-degree node, find first node with non-zero degree */
  if (lv >= nconn)
    for (lv = 0; lv < nconn; lv++)
      if (deg[lv]) break;

  /* find the eulerian path */
  find_path(lv);

  /* the path is discovered in reverse order */
  for (lv = plen-1; lv >= 0; lv--)
    printf ("%i\n", path[lv]+1);
  return 0;
}

--
       灬灬灬灬灬灬  灬灬 ════════════════════╗╮
   ╭╯  灬灬▂╱   ＿灬灬ジ  ヾ                                   灬╰╗
   ║ 灬◢◢ "▔ 灬╱          灵台无计逃神矢  风雨如磐暗故园  ▁  灬|"|║
   ║     ◤,  |,╱_ ◣◣      寄意寒星荃不察  我以我血荐轩辕▕心▏  ◣|║
   ║     _,|\▄/ \▌◥                                        ▔ヾ◥◥|║
   ╚═ "\▌| ▔ | | /" ════════════════════════╯

※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.111.200]

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店