首页 > 代码库 > acm1878欧拉回路

acm1878欧拉回路

2024-07-14 07:20:35   222人阅读

欧拉回路解释

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

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

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

 

 1 #include<iostream>  2 #include<cstring> 3 using namespace std; 4 const int maxn=1200; 5 int degree[maxn]; 6 int vis[maxn]; 7 int maze[maxn][maxn]; 8 int n,m; 9 void dfs(int i)10 {11     vis[i]=1;12     for(int j=1;j<=n;j++)13     {14         if(!vis[j]&&maze[i][j])15         {16             dfs(j);17         }18     }19     return;20 }21 int main()22 {23 24     int a,b;25     while(cin>>n&&n)26     {27         bool flag=false;28         cin>>m;29         memset(degree,0,sizeof(degree));30         memset(maze,0,sizeof(maze));31         memset(vis,0,sizeof(vis));32         for(int i=1;i<=m;i++)33         {34             cin>>a>>b;35             maze[a][b]=maze[b][a]=1;36             degree[a]++;37             degree[b]++;38         }39         for(int i=1;i<=n;i++)40         {41             if(degree[i]%2==1)42                 flag=true;43         }44         if(flag)45         {46             cout<<0<<endl;47             continue;48         }49         int p=0;50         for(int i=1;i<=n;i++)51         {52             if(!vis[i])53             {54                 p++;55                 dfs(i);56             }57         }58         if(p==1)cout<<1<<endl;59         else cout<<0<<endl; 60     }61     return 0;62 }

 


联系
我们