#1176 : 歐拉路·一

時(shí)間限制:10000ms 單點(diǎn)時(shí)限:1000ms 內(nèi)存限制:256MB

描述
小Hi和小Ho最近在玩一個(gè)解密類(lèi)的游戲，他們需要控制角色在一片原始叢林里面探險(xiǎn)，收集道具，并找到最后的寶藏。現(xiàn)在他們控制的角色來(lái)到了一個(gè)很大的湖邊。湖上有N個(gè)小島(編號(hào)1…N)，以及連接小島的M座木橋。每座木橋上各有一個(gè)寶箱，里面似乎裝著什么道具。

湖邊還有一個(gè)船夫，船夫告訴主角。他可以載著主角到任意一個(gè)島上，并且可以從任意一個(gè)島上再載著主角回到湖邊，但是主角只有一次來(lái)回的機(jī)會(huì)。同時(shí)船夫告訴主角，連接島嶼之間的木橋很脆弱，走過(guò)一次之后就會(huì)斷掉。

因?yàn)椴恢缹毾鋬?nèi)有什么道具，小Hi和小Ho覺(jué)得如果能把所有的道具收集齊肯定是最好的，那么對(duì)于當(dāng)前島嶼和木橋的情況，能否將所有道具收集齊呢？

舉個(gè)例子，比如一個(gè)由6個(gè)小島和8座橋組成的地圖：

主角可以先到達(dá)4號(hào)小島，然后按照4->1->2->4->5->6->3->2->5的順序到達(dá)5號(hào)小島，然后船夫到5號(hào)小島將主角接回湖邊。這樣主角就將所有橋上的道具都收集齊了。

提示：歐拉路的判定

輸入
第1行：2個(gè)正整數(shù)，N,M。分別表示島嶼數(shù)量和木橋數(shù)量。1≤N≤10,000，1≤M≤50,000

第2…M+1行：每行2個(gè)整數(shù)，u,v。表示有一座木橋連接著編號(hào)為u和編號(hào)為v的島嶼，兩個(gè)島之間可能有多座橋。1≤u,v≤N

輸出
第1行：1個(gè)字符串，如果能收集齊所有的道具輸出“Full”，否則輸出”P(pán)art”。

樣例輸入
6 8
1 2
1 4
2 4
2 5
2 3
3 6
4 5
5 6
樣例輸出
Full

涉及到的知識(shí)點(diǎn)：

歐拉通路定義：通過(guò)圖（無(wú)向圖或有向圖）中所有邊一次且僅一次 行遍所有的頂點(diǎn)的 通路稱(chēng)作歐拉通路。

歐拉回路的定義：通過(guò)圖中所有邊一次且僅一次行遍所有頂點(diǎn)的回路稱(chēng)為歐拉回路。

歐拉圖：具有歐拉回路 的 圖稱(chēng)為歐拉圖。

半歐拉圖：具有歐拉通路 的 圖稱(chēng)為半歐拉圖。

規(guī)定平凡圖【1階零圖【一條邊也沒(méi)有】】為歐拉圖。

定理1：無(wú)向圖是歐拉圖 當(dāng)且僅當(dāng)它是連通圖且沒(méi)有奇度頂點(diǎn)。

定理2：無(wú)向圖是半歐拉圖 當(dāng)且僅當(dāng)它是連通圖且恰有2個(gè)奇度頂點(diǎn)。

思路：

判斷歐拉通路：判斷它是否為歐拉圖或半歐拉圖即可。

本題是無(wú)向圖，認(rèn)真讀題，它給的一定是連通圖（所以無(wú)需判斷連通性），所以根據(jù)上述定理1和2只需要統(tǒng)計(jì)奇度頂點(diǎn)個(gè)數(shù)即可。

AC代碼：

#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 1e4+5; int d[N]; /* struct Edge {int from;int to;int nxt; }edge[N*5]; int head[N],idx; bool vis[N]; int total; void init() {memset(head,-1,sizeof(head));idx = 0; } void add_edge(int from,int to) {edge[idx].from = from;edge[idx].to = to;edge[idx].nxt = head[from];head[from] = idx++; } void dfs(int s) {for(int i = head[s]; ~i; i = edge[i].nxt){int to = edge[i].to;if(!vis[to]){vis[to] = true;total++;dfs(to);}} } */ int main() {int n,m;scanf("%d%d",&n,&m);//init();while(m--){int x,y;scanf("%d%d",&x,&y);d[x]++;d[y]++;//add_edge(x,y);//add_edge(y,x);}int cnt = 0;for(int i = 1; i <= n; i++){cnt += d[i] & 1;}bool flag = false;if(cnt == 0 || cnt == 2){/*vis[1] = true;total = 1;dfs(1);*/flag = true;}flag?puts("Full"):puts("Part");return 0; }

總結(jié)

以上是生活随笔為你收集整理的#1176 : 欧拉路·一（欧拉通路的判定）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。