一．无向图

欧拉回路：每个顶点度数都是偶数

欧拉路：所有点度数为偶数，或者只有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");

    }

}