歐拉路HDU3018

歐拉路，歐拉回路，講的實際上就是一筆畫的問題。

給定n個點，m條邊，如果能一筆把所有邊都連上就是歐拉路，如果起點和終點是同一點，就是歐拉回路。

歐拉路的特征：對于無向圖，如果所有點的度都是偶數，那么任意點都可以作為歐拉路的起點；如果存在兩個點的度是奇數，其他點的度都是偶數，那么這兩個分別作為歐拉路的起點和終點。

　　對于有向圖，如果每個點的入度和出度相同，一定能形成歐拉路；如果存在兩個點的入度和出度是奇數，以這兩個點為起點和終點可以形成一條歐拉路。4

　　判斷給定一個連通圖通過幾筆能畫出來：一筆畫能消去兩個度為奇數的點，如果沒有度為奇數的點，一筆就可以連通。

HDU3018

給定圖，多個連通圖，孤立的點忽略，不存在反身邊（就是自己連自己）。

用并查集記錄連通分支，分別計算各個連通分支上需要的筆畫數

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 100000+10;
 4 
 5 int pre[maxn],de[maxn];
 6 map<int,int>mp;
 7 map<int,int>s;
 8 int n,m,u,v;
 9 int f(int x){return x==pre[x]?x:pre[x]=f(pre[x]);}
10 void mix(int a,int b)
11 {
12     int x=f(a),y=f(b);
13     if(x!=y) pre[x]=y;
14 }
15 int main()
16 {
17     while(~scanf("%d%d",&n,&m))
18     {
19         for(int i=0;i<=n;i++)pre[i]=i;
20         memset(de,0,sizeof(de));
21         while(m--)
22         {
23             scanf("%d%d",&u,&v);
24             mix(u,v);
25             if(u!=v) {de[u]++;de[v]++;}
26         }
27         mp.clear();
28         s.clear();
29         int t=0;
30         for(int i=1;i<=n;i++)
31         {
32            if(tag[i]) t++;
33             else {
34             int p=f(i);
35                 if( de[i]&1 ) mp[p] ++;     //xia biao de  yi yi
36                 if(de[i]) s[p]=1;
37             }
38         }
39         int tot=0;
40         map<int,int>::iterator iter=mp.begin();
41         for(;iter!=mp.end();iter++)
42             tot=tot+iter->second / 2;
43         tot=tot+s.size()-mp.size();
44         cout<<tot<<endl;
45 
46     }
47     return 0;
48 }

View Code

轉載于:https://www.cnblogs.com/star-and-me/p/6885847.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/392749.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/392749.shtml
英文地址，請注明出處：http://en.pswp.cn/news/392749.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！