acm1878欧拉回路

对于本题我们只要把每个点的度进行记录，判断是否存在奇数度的点，如果是就可以判断不是欧拉回路，如果不是就在一个点出发，进行dfs搜索，

看能否走到起点，因为对于欧拉回路是一个闭合的回路，无论在哪个点出发都应当可以走回起点，所以一次性遍历必将经过每个点，如果出现没有

走过的点，则不是欧拉回路。

 #include<iostream>

 #include<cstring>

 using namespace std;

 const int maxn=;

 int degree[maxn];

 int vis[maxn];

 int maze[maxn][maxn];

 int n,m;

 void dfs(int i)

 {

     vis[i]=;

     for(int j=;j<=n;j++)

     {

         if(!vis[j]&&maze[i][j])

         {

             dfs(j);

         }

     }

     return;

 }

 int main()

 {

     int a,b;

     while(cin>>n&&n)

     {

         bool flag=false;

         cin>>m;

         memset(degree,,sizeof(degree));

         memset(maze,,sizeof(maze));

         memset(vis,,sizeof(vis));

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

         {

             cin>>a>>b;

             maze[a][b]=maze[b][a]=;

             degree[a]++;

             degree[b]++;

         }

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

         {

             if(degree[i]%==)

                 flag=true;

         }

         if(flag)

         {

             cout<<<<endl;

             continue;

         }

         int p=;

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

         {

             if(!vis[i])

             {

                 p++;

                 dfs(i);

             }

         }

         if(p==)cout<<<<endl;

         else cout<<<<endl;

     }

     return ;

 }

巴特西

acm1878欧拉回路

最新文章

热门文章