首页 > 代码库 > 欧拉路HDU3018

欧拉路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

 

欧拉路HDU3018