HDU NO.1878 欧拉回路（邻接矩阵，判断欧拉回路的条件）
发布时间
阅读量：
阅读量
题意：（中文略）
思路：
存在欧拉回路的充要条件是每一个顶点的度数均为偶数，并且该图必须是连通的。此外，在任何一点都可以在整个图中被访问到的情况下，这样的结构才能满足欧拉回路的要求。
这一类问题利用邻接矩阵比较方便。
原题描述：
Description
欧拉回路被称为不允许笔离开纸面的情况下能够遍历图中的每一条边恰好一次的一种闭合路径，并且回到起点形成一个闭合的循环结构。对于给定的一个图来说，请判断是否存在这样的欧拉回路？
Input
测试输入包含多个测试案例。每个测试案例的第一行给出了两个正整数（其中 1 < N < 1000），分别表示图中的顶点数目N以及边的数量M；接下来的M行分别描述了每一条边的信息——每条边由一对正整数组成，并指定了连接该条边两端顶点的具体编号（这些顶点从1到N编号）。特别地，在节点总数为零时指示结束状态。
Output
每个测试用例的输出占一行，若欧拉回路存在则输出1，否则输出0。
Sample Input
3 3 1 2 1 3 2 3 3 2 1 2 2 3 0Sample Output
1 0AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<stack>
#include<cstring>
#include<string>
#include<vector>
#include<set>
using namespace std;
#define X first
#define Y second
const int INF = 0x3f3f3f3f;
const int MAX = 1010;
int head[MAX];
int m, n;
int degree[MAX], Map[MAX][MAX];
bool vis[MAX];
void init(){
memset(vis, 0, sizeof(vis));
memset(Map, 0, sizeof(Map));
memset(degree, 0, sizeof(degree));
}
void dfs(int now){
vis[now] = 1;
for(int i = 1; i <= m; i++){
if(!vis[i] && Map[now][i])
dfs(i);
}
}
bool check(){
bool flag = true;
for(int i = 1; i <= m; i++)
if(indegree[i] % 2)
flag = false;
return flag;
}
int main(){
while(scanf("%d", &m) && m){
scanf("%d", &n);
init();
int a, b;
for(int i = 0; i < n; i++){
scanf("%d%d", &a, &b);
Map[a][b] = Map[b][a] = 1;
degree[a]++;
degree[b]++;
}
dfs(1);
int k;
for(k = 1; k <= m; k++){
if(!vis[k])
break;
}
if(check() && k > m)
printf("1\n");
else
printf("0\n");
}
return 0;
}全部评论 (0)
还没有任何评论哟~