题意：有很多路，问能否每条路只走一遍、恰好回到起点？

思路：无向图的欧拉回路的应用。但是是神坑的一道题~  

注意：考虑下面的数据

Input:
3 2
0 1
1 0

2 2
1 0
1 0

4 4
0 1
1 0
2 3
3 2

5 6
0 1
1 0
2 3
2 3
0 2
2 0

4 6
1 2
2 1
2 3
2 3
3 1
1 3

2 0

Output:
Possible
Possible
Not Possible
Possible
Possible
Not Possible

也就是说，第一，只要把所有的边访问就行了，可以存在一些没有访问的顶点。

第二，r==0时是Not Possible的（没有路径时就不能访问所有的边，因为没有边可访问；但是没有路径时也等于可以访问所有的边，因为没有边是没有访问的。。感觉和第一条的逻辑有些矛盾！！）

第三，输入数据可能存在自回路，也就是 1 1这样的边，它是考虑到有一条路是圆形的吗？？（这个导致了版本一的RE错误）

反正就是感觉数据太坑了~~

首先，提交的是版本一，在判断连通性时，我没有用vis数组来判断一个顶点是否访问过，而是用顶点的度数是否为0来判断，因为每次访问一条边后、删除这条边时会减少相应顶点的度数。但是在输入时我用的graph[u][v]++;graph[v][u]=graph[u][v]; 提交后RE错误，由于题目在终止输入时没有说清，改了几次输入如下代码所示，变成了WA。

Code：

//版本一，AC
#include<stdio.h>
#include<string.h>

void dfs(int u,int n);
bool solve(int n);

int du[205];
int graph[205][205];

int main()
{
  int n,r;
  //scanf("%d%d",&n,&r);
  //while(scanf("%d%d",&n,&r)==2 && n && r)
  while(scanf("%d%d",&n,&r)==2)
  {
    memset(du,0,sizeof(du));
    memset(graph,0,sizeof(graph));
    for(int i=0;i<r;++i)
    {
      int u,v;
      scanf("%d%d",&u,&v);
      graph[u][v]++;
      //graph[v][u]=graph[u][v];
      graph[v][u]++;
      du[u]++;
      du[v]++;      
    }
    if(solve(n)) printf("Possible\n");
    else printf("Not Possible\n");                  
  }
  return 0;
}

bool solve(int n)
{
  for(int i=0;i<n;++i)
  {
    if(du[i]&1) return false;
  }  
  
  int cnt=0;
  for(int i=0;i<n;++i)
  {
    if(du[i])
    { cnt++; dfs(i,n);}      
  }//printf("cnt:%d\n",cnt);
  if(cnt!=1) return false;
  return true;
}

void dfs(int u,int n)
{
  for(int v=0;v<n;++v)
  {
    if(graph[u][v])
    { //删除无向边
      graph[u][v]--;
      graph[v][u]--; 
      du[u]--;
      du[v]--;
      dfs(v,n);             
    }      
  }   
}

//WA，别再修改 
#include<stdio.h>
#include<string.h>

void dfs(int u,int n);
bool solve(int n);

int du[205];
int graph[205][205];

int main()
{
  int n,r;
  //scanf("%d%d",&n,&r);
  //while(scanf("%d%d",&n,&r)==2 && n && r)
  while(scanf("%d%d",&n,&r)==2)
  {
    memset(du,0,sizeof(du));
    memset(graph,0,sizeof(graph));
    for(int i=0;i<r;++i)
    {
      int u,v;
      scanf("%d%d",&u,&v);
      graph[u][v]++;
      //graph[v][u]=graph[u][v];
      graph[v][u]++;//自回路 
      du[u]++;
      du[v]++;      
    }
    if(solve(n)) printf("Possible\n");
    else printf("Not Possible\n");                  
  }
  return 0;
}

bool solve(int n)
{
  for(int i=0;i<n;++i)
  {
    if(du[i]&1 || du[i]==0) return false;
  }  
  
  dfs(0,n);
  for(int i=0;i<n;++i)
  { if(du[i]) return false; } 
  return true;
}

void dfs(int u,int n)
{
  for(int v=0;v<n;++v)
  {
    if(graph[u][v])
    { //删除无向边
      graph[u][v]--;
      graph[v][u]--; 
      du[u]--;
      du[v]--;
      dfs(v,n);             
    }      
  }   
}

<pre name="code" class="cpp">//AC
#include<stdio.h>
#include<string.h>

void dfs(int u,int n);
bool solve(int n);

int du[205];
int graph[205][205];
int vis[205];

int main()
{
  int n,r;
  //scanf("%d%d",&n,&r);
  //while(scanf("%d%d",&n,&r)==2 && n && r)
  while(scanf("%d%d",&n,&r)==2)
  {
    memset(du,0,sizeof(du));
    memset(graph,0,sizeof(graph));
    memset(vis,0,sizeof(vis));
    for(int i=0;i<r;++i)
    {
      int u,v;
      scanf("%d%d",&u,&v);
      graph[u][v]++;
      //graph[v][u]=graph[u][v];
      graph[v][u]++;//自回路 
      du[u]++;
      du[v]++;      
    }
    if(r && solve(n)) printf("Possible\n");
    else printf("Not Possible\n");                  
  }
  return 0;
}

bool solve(int n)
{
  for(int i=0;i<n;++i)
  {
    if(du[i]&1) return false;
  }  
  
  for(int i=0;i<n;++i)
  {
    if(du[i])
    {
      vis[i]=1;
      dfs(i,n);
      break;       
    }      
  }
  for(int i=0;i<n;++i)
  { if(du[i] && !vis[i]) return false; } 
  return true;
}

void dfs(int u,int n)
{
  for(int v=0;v<n;++v)
  {
    if(!vis[v] && graph[u][v])
    {
       vis[v]=1;
       dfs(v,n);
    }      
  }   
}

UVa 10596 清晨漫步