歐拉回路就是用一筆走過所有的路，現(xiàn)在讓你判斷到底有幾個(gè)歐拉回路，也就是說走一個(gè)圖需要用幾筆。

傳送門QAQ

首先根據(jù)給出的邊我們只需要分別處理每個(gè)連通分量需要多少筆即可.

? ? ? ? 如果該連通分量是一個(gè)孤立的點(diǎn),顯然只需要0筆.

? ? ? ? 如果該連通分量是一個(gè)歐拉圖或半歐拉圖,只需要1筆.

? ? ? ? 現(xiàn)在關(guān)鍵是連通分量并非一個(gè)(半)歐拉圖時(shí),需要幾筆?

? ? ? ? 一般性的結(jié)論是:

? ? ? ?非(半)歐拉圖需要的筆數(shù)==該圖中奇數(shù)度的點(diǎn)數(shù)目/2

? ? ? ?下面來證明該結(jié)論:

? ? ? ?首先一個(gè)無向圖的連通分量中的奇數(shù)度的點(diǎn)個(gè)數(shù)一定是偶數(shù)個(gè)(成對(duì)出現(xiàn)),因?yàn)闊o向圖的總度數(shù)=偶數(shù).

? ? ? ?我們?cè)谶@種連通分量中每次畫一筆有兩種選擇:

? ? ? ?1.a->b->c->d…->g??? 一條起點(diǎn)與終點(diǎn)不同的路徑(路中除首尾度減1外,每個(gè)點(diǎn)度減2)

? ? ? ?2.a->b->c->d…->a??? 一條起點(diǎn)與終點(diǎn)相同的回路(路中每個(gè)點(diǎn)度數(shù)減2)

? ? ? ?也就是說想要把非(半)歐拉圖分量中的奇數(shù)度的點(diǎn)的度數(shù)都變成偶數(shù),我們至少需要畫奇數(shù)度點(diǎn)個(gè)數(shù)/2 筆.

? ? ? ?那么對(duì)于這種圖我們最多需要畫的筆數(shù) 是不是也是 : 奇數(shù)度點(diǎn)個(gè)數(shù)/2 筆呢?

? ? ? ?答案是肯定的,這里假設(shè)圖中有4個(gè)奇數(shù)度的點(diǎn),1,2,3,4,5,6.如下圖所示:

?

? ? ? ?我們先走路:1-> b-> c-> d-> e-> f->a-> 2 這條路.然后6,5 和3,4 分別屬于兩個(gè)連通分量了.可以看出只需要3筆,即6/2=3即可.

? ? ? ?也就是說對(duì)于這種非(半)歐拉圖的連通分量,我們每筆必然消除正好2個(gè)點(diǎn)的奇度(使其度變偶數(shù)),當(dāng)最后一筆的時(shí)候我們必然消除所有的點(diǎn)的度數(shù)(包括剩下的兩個(gè)奇點(diǎn),因?yàn)樽詈笠还P就必然是歐拉通路).但是有一點(diǎn)要注意,有可能過程中的某幾筆會(huì)使得該連通分量變成多個(gè)連通分量,當(dāng)然結(jié)論不變.

?????? 經(jīng)過上面的分析,這題的結(jié)論出來了,對(duì)于每個(gè)以i為根的連通分量我們記錄屬于該連通分量的點(diǎn)數(shù)目num[i]和該連通分量中奇度點(diǎn)的個(gè)數(shù)odd[i].

?????? 如果num[i]==0或1,需0筆.(注意num[i]==0表示i點(diǎn)不是根,num[i]==1表示i點(diǎn)是一個(gè)孤立的點(diǎn).)

?????? 如果num[i]>1且odd[i]==0 需1筆

?????? 如果num[i]>1且odd[i]>0 需odd[i]/2筆

1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<map> 6 #include<set> 7 #include<vector> 8 #include<queue> 9 #include<algorithm> 10 #include<cmath> 11 using namespace std; 12 #define ll long long 13 const int N = 100000 + 10; 14 int n, m,xx,yy; 15 int fa[N], indu[N], odd[N],num[N]; 16 int find(int x) 17 { 18 if (fa[x] == -1) return x; 19 return fa[x] = find(fa[x]); 20 } 21 void hebing(int a, int b) 22 { 23 a = find(a); 24 b = find(b); 25 if(a!=b) 26 fa[a] = b; 27 } 28 int main() 29 { 30 while (scanf("%d %d", &n, &m) != EOF) 31 { 32 memset(fa, -1, sizeof(fa)); 33 memset(indu, 0, sizeof(indu)); 34 memset(odd, 0, sizeof(odd)); 35 memset(num, 0, sizeof(num)); 36 while (m--) 37 { 38 scanf("%d %d",&xx,&yy); 39 indu[xx]++; 40 indu[yy]++; 41 hebing(xx, yy); 42 } 43 for (int i = 1; i <= n; i++) 44 { 45 num[find(i)]++; 46 if (indu[i] % 2 == 1) 47 odd[find(i)]++; 48 } 49 int ans = 0; 50 for (int i = 1; i <= n; i++) 51 { 52 if (num[i] <= 1) continue; 53 if (odd[i] == 0) ans += 1; 54 else ans += odd[i] / 2; 55 } 56 printf("%d\n",ans); 57 } 58 59 return 0; 60 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/Kaike/p/10417939.html

總結(jié)

以上是生活随笔為你收集整理的[图论]欧拉回路的个数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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