一．无向图
欧拉回路：每个顶点度数都是偶数
欧拉路：所有点度数为偶数，或者只有2个点度数为奇数
当然判连通性
hdu 1878 欧拉回路 两种判连通的方法
dfs
#include <iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define N 1010
int degree[N],n,m;
bool visit[N];
vector<int>edge[N];
void dfs(int point){
int i,j,p;
visit[point]=1;
for(i=0;i<edge[point].size();i++){
p=edge[point][i];
if(!visit[p])
dfs(p);
}
}
int main(int argc, char** argv) {
int i,j,a,b;
while(scanf("%d",&n)!=EOF&&n){
scanf("%d",&m);
for(i=1;i<=n;i++){
degree[i]=0;
edge[i].clear();
}
for(i=0;i<m;i++){
scanf("%d%d",&a,&b);
if(a!=b){
edge[a].push_back(b);
edge[b].push_back(a);
degree[a]++;
degree[b]++;
}
}
bool flag=0;
for(i=1;i<=n;i++){
if(degree[i]&1){
printf("0\n");
flag=1;
break;
}
}
if(flag)
continue;
memset(visit,0,sizeof(visit));
dfs(1);
for(i=1;i<=n;i++){
if(!visit[i]){
flag=1;
break;
}
}
if(flag)
printf("0\n");
else
printf("1\n");
}
return 0;
}
并查集:
#include <iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define N 1010
int degree[N],n,m;
vector<int>edge[N];
int father[N];
int find(int x){
while(x!=father[x])
x=father[x];
return x;
}
void unite(int a,int b){
father[b]=find(a);
}
int main(int argc, char** argv) {
int i,j,a,b;
while(scanf("%d",&n)!=EOF&&n){
scanf("%d",&m);
for(i=1;i<=n;i++){
degree[i]=0;
edge[i].clear();
father[i]=i;
}
for(i=0;i<m;i++){
scanf("%d%d",&a,&b);
if(a!=b){
edge[a].push_back(b);
edge[b].push_back(a);
degree[a]++;
degree[b]++;
if(find(a)!=find(b))
unite(a,b);
}
}
bool flag=0;
for(i=1;i<=n;i++){
if(degree[i]&1){
printf("0\n");
flag=1;
break;
}
}
if(flag)
continue;
int x=father[1];
for(i=2;i<=n;i++){
if(find(i)!=x){
flag=1;
break;
}
}
if(flag)
printf("0\n");
else
printf("1\n");
}
}