杭電ACM1878――歐拉回路
來源：程序員人生 發布時間：2015-08-06 10:24:49 閱讀次數：3480次
簡單的歐拉回路，如題。
歐拉回路的判斷：
1.在有向圖中：首先必要的條件是圖連通，所以頂點的入度都等于出度。
2.在無向圖中：重要條件還是圖連通，其次就是所以頂點都是偶數度（該頂點的度為偶數）
這1題是無向圖，所以根據判斷方法來寫，很簡單，判定就不證明了。
我是用并查集來判斷圖是不是連通的。
下面是AC的代碼：
#include <iostream>
#include <cstring>
using namespace std;
int par[1005], degree[1005];
int finds(int x)
{
if(x == par[x])
return x;
else
return par[x] = finds(par[x]);
}
int main()
{
int a, b, n, m, i;
while(cin >> n)
{
if(n == 0)
break;
for(i = 0; i <= n; i++)
par[i] = i;
memset(degree, 0, sizeof(degree));
cin >> m;
for(i = 0; i < m; i++)
{
cin >> a >> b;
degree[a]++; //該點度+1
degree[b]++;
int x = finds(a);
int y = finds(b);
if(x != y) //合并
par[x] = y;
}
int flag = 0, tag = 0;
for(i = 1; i <= n; i++) //判是不是連通
if(par[i] == i)
flag++;
if(flag > 1)
cout << 0 << endl;
else
{
for(i = 1; i <= n; i++) //判頂點的度是不是為偶數
{
if(degree[i] % 2)
tag++;
}
if(tag > 0)
cout << 0 << endl;
else
cout << 1 << endl;
}
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
