NOJ 42题 一笔画（欧拉回路）

题目链接~~>

         欧拉道路：从图中的一个结点出发走出一条道路，每条边恰好经过一次（不一定回到出发点）。条件：连通且含有两个奇点。

         欧拉回路：从图中的一个结点出发走出一条道路，每条边恰好经过一次，且最终又回到出发点。条件：连通且含有零个奇点。

打印道路代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      int map[102][102];
     
    
   

    

     

    
    

     

      int n;
     
    
   

    

     

    
    

     

      void euler(int u)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(int v=1;v<=n;v++)
     
    
   

    

     

    
    

     
 if(map[u][v])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 map[u][v]=map[v][u]=0;//无向图
     
    
   

    

     

    
    

     
 //map[u][v]=0; 有向图
     
    
   

    

     

    
    

     
 printf("~%d %d",u,v);
     
    
   

    

     

    
    

     

       euler(v);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int T,m,i,x,y;
     
    
   

    

     

    
    

     
 scanf("%d",&T);
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d",&n,&m);
     
    
   

    

     

    
    

     
 memset(map,0,sizeof(map));
     
    
   

    

     

    
    

     
 for(i=0;i<m;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d",&x,&y);
     
    
   

    

     

    
    

     
 map[x][y]=map[y][x]=1;//无向图
     
    
   

    

     

    
    

     
 //map[x][y]=1; 有向图
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       euler(1);//如果欧拉回路可以传任意一个点，否则传奇数点
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

 代码（NOJ 一笔画）：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      int n;
     
    
   

    

     

    
    

     

      int vis[1002],father[1002];
     
    
   

    

     

    
    

     

      int find(int x)//寻找父亲
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(father[x]!=x)
     
    
   

    

     

    
    

     

       x=find(father[x]);
     
    
   

    

     

    
    

     
 return x ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int T,i,m,x,y,fx,fy;
     
    
   

    

     

    
    

     
 scanf("%d",&T);
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d",&n,&m);
     
    
   

    

     

    
    

     
 int q=0;
     
    
   

    

     

    
    

     
 memset(vis,0,sizeof(vis));
     
    
   

    

     

    
    

     
 for(i=1;i<=n;i++)
     
    
   

    

     

    
    

     

       father[i]=i;
     
    
   

    

     

    
    

     
 for(i=0;i<m;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d",&x,&y);
     
    
   

    

     

    
    

     

       vis[x]++;vis[y]++;//判断是奇点还是偶点
     
    
   

    

     

    
    

     

       fx=find(x);fy=find(y);
     
    
   

    

     

    
    

     
 if(fx!=fy)//判断图是否连通
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       father[fx]=fy;
     
    
   

    

     

    
    

     

       q++;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(q<n-1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf("No\n");
     
    
   

    

     

    
    

     
 continue;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int fg=0;
     
    
   

    

     

    
    

     
 for(i=1;i<=n;i++)
     
    
   

    

     

    
    

     
 if(vis[i]%2)
     
    
   

    

     

    
    

     

       fg++;
     
    
   

    

     

    
    

     
 if(fg>2)
     
    
   

    

     

    
    

     
 printf("No\n");
     
    
   

    

     

    
    

     
 else printf("Yes\n");
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/9629203