南陽理工ACM42――一筆畫問題
來源：程序員人生 發布時間：2015-05-13 08:22:24 閱讀次數：2652次
1筆劃問題，也就是歐拉道路，這1題，簡單的歐拉回路的利用。
甚么是歐拉回路？
歐拉回路就是在圖A中，存在1條路徑使得每條邊都走過1次，并且這條路徑是1個圈，就是歐拉回路。
歐拉回路的判斷：
1.在有向圖中：首先必要的條件是圖連通，所以頂點的入度都等于出度。
2.在無向圖中：重要條件還是圖連通，其次就是所以頂點都是偶數度（該頂點的度為偶數）
這1題，還需要加上1個條件，也就是存在兩個奇數度的點的情況，也是符合的，從1個奇數點動身，另外1個奇數點結束。
判斷圖是不是連通，可以應用DFS或并查集，都是很簡單的。
下面是dfs的算法：
void dfs(int x)
{
int i;
vis[x] = 1; //標記已返問過
for(i = 1; i <= n; i++)
if(map[x][i])
{
degree[x]++; //該點度+1
if(vis[i] == 0) //沒返問過，遞歸
dfs(i);
}
}
下面是AC的代碼，我用的是并查集來判連通：
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 1005;
int par[MAX_N], degree[MAX_N], n, v;
int finds(int x)
{
if(x == par[x])
return x;
else
return par[x] = finds(par[x]);
}
int main()
{
// freopen("data.txt", "r", stdin);
int t, a, b, i, j;
cin >> t;
while(t--)
{
cin >> n >> v;
memset(degree, 0, sizeof(degree));
for(j = 0; j <= n; j++) //初始化并查集
par[j] = j;
for(i = 0; i < v; i++)
{
cin >> a >> b;
degree[a]++; degree[b]++; //該點度+1
int next_a = finds(a);
int next_b = finds(b);
if(next_a != next_b) //合并
par[next_a] = next_b;
}
int flag = 0, tag = 0;
for(i = 1; i <= n; i++) //判連通
if(par[i] == i)
flag++;
if(flag > 1) //不連通
cout << "No" << endl;
else //連通
{
for(i = 1; i <= n; i++) //判奇數點
if(degree[i] % 2)
tag++;
if(tag == 0 || tag == 2)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
