首页 > 其他 > 详细

图论之欧拉路问题

时间：2021-08-23 15:05:30      阅读：34      评论：0      收藏：0      [点我收藏+]

　　今天继续划水，来讲一讲欧拉路问题。

　　欧拉路，简单来说就是一笔画，即对于一张图，可以从某个点出发，经过每一条边，遍历完整张图，这个路径就称为欧拉路径。如果起点与终点重合，则称为欧拉回路。那么，应该如何判断欧拉路呢？

　　我们先定义几个概念，在无向图中，我们称有奇数条连接的边的点为奇点，有偶数条连接的边的点为偶点。对于有向图，我们设度数为出度减入度的值。

　　首先，应该判断连通性（dfs），如果这一个图不连通，则一定不是欧拉路。之后从其是否有向进行判断。

　　1.对于无向连通图，若节点全部为偶点，那么是欧拉回路，若只有两个奇点，其余全部为偶点，那么是欧拉路。

　　2.对于有向连通图，若所有的节点度数都为0，那么是欧拉回路，若起点度数为1，终点度数为-1，其余节点度数全部为0，那么是欧拉路。

例题1 hdu1878

欧拉回路

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 23884    Accepted Submission(s): 9310

Problem Description
欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？
Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数N ( 1 < N < 1000 )和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。当N为0时输入结
束。
Output
每个测试用例的输出占一行，若欧拉回路存在则输出1，否则输出0。
Sample Input
3 3
1 2
1 3
2 3
3 2
1 2
2 3
0
Sample Output
1
0
　　模板题
　　代码如下
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1005;
 4 using ll = long long;
 5 int du[maxn];
 6 bool vis[maxn];
 7 vector<int> g[maxn];
 8 void dfs(int x){
 9     vis[x]=1;
10     for(int i=0;i<g[x].size();i++){
11         if(!vis[g[x][i]])dfs(g[x][i]);
12     }
13 } 
14 int main() {
15     ios::sync_with_stdio(false);
16     cin.tie(0);
17     cout.tie(0);
18     int n,m;
19     while(1){
20         cin>>n;
21         if(n==0)break;
22         cin>>m;
23         memset(du,0,sizeof(du));
24         for(int i=1;i<=n;i++)g[i].clear();
25         memset(vis,0,sizeof(vis));
26         while(m--){
27             int x,y;
28             cin>>x>>y;
29             g[x].push_back(y);
30             g[y].push_back(x);
31             du[x]++;
32             du[y]++;
33         }
34         int flag=1;
35         for(int i=1;i<=n;i++){
36             if(du[i]&1){
37                 flag=0;
38                 break;
39             }
40         }
41         dfs(1);
42         for(int i=1;i<=n;i++){
43             if(!vis[i]){
44                 flag=0;
45                 break;
46             }
47         }
48         cout<<flag<<endl;
49     }
50     return 0;
51 }

例题2 hdu1116

Play on Words

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 12319    Accepted Submission(s): 4314

Problem Description
Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.
There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word ``acm‘‘ can be followed by the word ``motorola‘‘. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.
Input
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number Nthat indicates the number of plates (1 <= N <= 100000). Then exactly Nlines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters ‘a‘ through ‘z‘ will appear in the word. The same word may appear several times in the list.
Output
Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times.
If there exists such an ordering of plates, your program should print the sentence "Ordering is possible.". Otherwise, output the sentence "The door cannot be opened.".
Sample Input
3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok
Sample Output
The door cannot be opened.
Ordering is possible.
The door cannot be opened.
　　题目大意就是给多个字符串，若两个字符串首尾元素相同，则可以连接，问给定的字符串能否连接为一个字符串。
　　这题是一道有向图欧拉路问题，我们可以建立首元素指向末尾元素的边，然后查看这张图是否是欧拉路即可。
　　代码如下
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 using ll = long long;
 4 const int maxn=30;
 5 vector<int>g[maxn];
 6 bool vis[maxn];
 7 bool exi[maxn];
 8 int du[maxn]={0};
 9 void dfs(int x){
10     vis[x]=1;
11     for(int i=0;i<(int)g[x].size();i++){
12         int nex=g[x][i];
13         if(!vis[nex])dfs(nex);
14     }
15 }
16 int main() {
17     ios::sync_with_stdio(false);
18     cin.tie(0);
19     cout.tie(0);
20     int t;
21     cin>>t;
22     while(t--){
23         int m;
24         cin>>m;
25         int flag=1;
26         memset(exi,0,sizeof(exi));
27         memset(du,0,sizeof(du));
28         memset(exi,0,sizeof(exi));
29         memset(vis,0,sizeof(vis));
30         for(int i=0;i<maxn;i++)g[i].clear();
31         while(m--){
32             string s;
33             cin>>s;
34             int x=s[0]-‘a‘,y=s[s.size()-1]-‘a‘;
35             g[x].push_back(y);
36             du[x]++;
37             du[y]--;
38             exi[x]=1;
39             exi[y]=1;
40         }
41         int cnt1=0;
42         int cnt2=0;
43         int cnt3=0;
44         int start=0;
45         for(int i=0;i<=25;i++){
46             if(du[i]==1){
47                 cnt1++;
48                 start=i;
49             }
50             if(du[i]==-1)cnt2++;
51             if(du[i]!=1&&du[i]!=0&&du[i]!=-1)cnt3++;
52         }
53         if((cnt1==1&&cnt2==1) || (cnt1==0&&cnt2==0))flag=1;
54         else flag=0;
55         if(cnt1&&cnt2&&(cnt1+cnt2>2))flag=0;
56         if(cnt3>0)flag=0;
57         dfs(start);
58         for(int i=0;i<=25;i++){
59             if(exi[i]&&(!vis[i]))flag=0;
60         }
61         if(flag)cout<<"Ordering is possible."<<endl;
62         else cout<<"The door cannot be opened."<<endl;
63     }
64     return 0;
65 }

例题3 hdu5883

The Best Path

Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 3419    Accepted Submission(s): 1388

Problem Description
Alice is planning her travel route in a beautiful valley. In this valley, there are N lakes, and M rivers linking these lakes. Alice wants to start her trip from one lake, and enjoys the landscape by boat. That means she need to set up a path which go through every river exactly once. In addition, Alice has a specific number (a1,a2,...,an) for each lake. If the path she finds is P0→P1→...→Pt, the lucky number of this trip would be aP0XORaP1XOR...XORaPt. She want to make this number as large as possible. Can you help her?
Input
The first line of input contains an integer t, the number of test cases. t test cases follow.
For each test case, in the first line there are two positive integers N (N≤100000) and M (M≤500000), as described above. The i-th line of the next N lines contains an integer ai(?i,0≤ai≤10000) representing the number of the i-th lake.
The i-th line of the next M lines contains two integers ui and vi representing the i-th river between the ui-th lake and vi-th lake. It is possible that ui=vi.
Output
For each test cases, output the largest lucky number. If it dose not have any path, output "Impossible".
Sample Input
2
3 2
3 4
5
1 2
2 3
4 3
1
2
3
4
1 2
2 3
2 4
Sample Output
2
Impossible
　　题目大意：给定一张图以及每个顶点的点权，要求一遍跑完这张图的所有边，得到的答案为所有经过的点的点权的异或和的最大值，若不可以跑完，输出impossible。
　　题解：先判断是否是欧拉路，若是欧拉路，我们再考虑如果它不是欧拉回路，那么明显答案唯一，就是从起点到终点的异或和，如果是欧拉回路，我们仔细观察，会发现既然可以以任何一个节点作为起点，该起点同时也是终点，即只有这一个点异或了两次，故而答案就是求所有节点异或和分别与每个节点异或之后的值的最大值。
　　代码如下 
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn=(1e5)+5;
 5 const int maxm=(5e5)+5;
 6 ll a[maxn];
 7 ll du[maxn];
 8 int main(){
 9     int t;
10     cin>>t;
11     while(t--){
12         int n,m;
13         memset(du,0,sizeof(du));
14         scanf("%d%d",&n,&m);
15         for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
16         for(int i=1;i<=m;i++){
17             ll x,y;
18             scanf("%lld%lld",&x,&y);
19             du[x]++;
20             du[y]++;
21         }
22         int cnt=0;
23         int start;
24         for(int i=1;i<=n;i++){
25             if(du[i]&1){
26                 cnt++;
27                 start=i;
28             }
29         }
30         bool flag=1;
31         ll ans=0;
32         if(cnt==2){  //欧拉通路 
33             for(int i=1;i<=n;i++){
34                 for(int j=1;j<=du[i]/2;j++){
35                     ans^=a[i];
36                 }
37                 if(du[i]&1)ans^=a[i];
38             }
39         }
40         else if(cnt==0){  //欧拉回路 
41             for(int i=1;i<=n;i++){
42                 for(int j=1;j<=du[i]/2;j++){
43                     ans^=a[i];
44                 }
45             }
46             int ans0=ans;
47             for(int i=1;i<=n;i++){
48                 ans=max(ans0,ans0^a[i]);
49             }
50         }
51         else flag=0;
52         if(flag)printf("%lld\n",ans);
53         else printf("Impossible\n");
54     }
55     return 0;
56 }

 

图论之欧拉路问题

原文：https://www.cnblogs.com/yokino/p/15175360.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！