无向图的欧拉回路和欧拉通路

//首先我认为需要区分的概念是欧拉回路和欧拉通路(算法竞赛入门经典中是欧拉道路),
//无向图:
//欧拉回路,即从无向图的一个节点出发每条边仅经过一次后,可以回到起点的一条回路
//判断方法:1.该无向图连通,这步bfs一次即可2.每个点的度数是偶数
//欧拉通路(欧拉道路),即从无向图的一个节点走出一条道路,每条边恰好经过一次(即不一定要返回起点)
//判断方法1.该无向图连通2.每一个点的度数是0(欧拉回路当然是欧拉通路)或含有2个度数那就只能从一个奇点出发经过其他边另一个奇点为止
//欧拉图:具有欧拉回路的图是欧拉图
//练习:Hdu 1878 欧拉回路

//http://acm.hdu.edu.cn/showproblem.php?pid=1878

ac代码:

#include
#include
#include
using namespace std;
queueq;
 int n;
 int indegree[1001];
 int a[1001][1001];
 int panduan()
 {
     int i;
     for (i=1;i<=n;i++)
        if (indegree[i]%2)
        return 1;
       return 0;
 }
 int bfs()
 {
     int vis[1001];
     int i,j,temp;
     q.push(1);
     for (i=1;i<=n;i++)
        vis[i]=0;
     while(!q.empty())
     {

         temp=q.front();
         q.pop();
         for (i=1;i<=n;i++)
            if ((a[temp][i])&&(!vis[i]))
            {

                vis[i]=1;
                q.push(i);

            }
     }
     for (i=1;i<=n;i++)
        if (vis[i]==0)
       return 0;
     return 1;

 }
  int main()
  {

      int m,c,d,i,j;

     while(scanf("%d%d",&n,&m)==2)
      {
          for (i=1;i<=n;i++)
          indegree[i]=0;
          for (i=1;i<=n;i++)
            for (j=1;j<=n;j++)
            a[i][j]=0;
          for (i=1;i<=m;i++)
          {

              scanf("%d%d",&c,&d);
              a[c][d]=1;
              a[d][c]=1;
              indegree[c]++;
              indegree[d]++;

          }
          if (panduan())
            printf("0\n");
          else
             if (bfs())
             printf("1\n");
          else
            printf("0\n");
      }
          return 0;
}




你可能感兴趣的