3 3 1 2 1 3 2 3 3 2 1 2 2 3 0
1 0
一上来我直接用递归暴搜,结果超时:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 1005 int N,M; int a,b; int map[MAX][MAX]; bool vis[MAX]; bool dfs(int k,int n){ if(n==N){ if(map[k][a])return true; else return false; } for(int i=1;i<=N;i++){ if(map[k][i]&&!vis[i]){ vis[i]=true; if(dfs(i,n+1))return true; vis[i]=false; } } return false; } int main(){ //freopen("C:\\in.txt","r",stdin); while(~scanf("%d",&N)&&N){ scanf("%d",&M); memset(map,0,sizeof(map)); memset(vis,0,sizeof(vis)); for(int i=0;i<M;i++){ scanf("%d%d",&a,&b); map[a][b]=map[b][a]=1; } vis[a]=true; printf("%d\n",dfs(a,1)); } return 0; } /************************************************************** Problem: 1027 User: starcuan Language: C++ Result: Time Limit Exceed ****************************************************************/
1、欧拉回路必须能从1一直能连线到n的连通图,所以用并查集的话,就只能有1个集合
2、欧拉回路:
有向图:所有的顶点出度=入度。
无向图:所有顶点都是偶数度。
满足上面两个条件的话就一定是欧拉回路
所以,利用并查集和节点度数的奇偶判断就可知是否是欧拉回路
/* 题目1027:欧拉回路 */ #include <iostream> #include <string.h> using namespace std; #define MAX 1005 int N,M; int a,b; int field[MAX]; int degree[MAX]; int find(int x) { if(field[x]==0) return x; field[x] = find(field[x]); return field[x]; } void make(int x,int y)//将x与y合并 { int f1=find(x); int f2=find(y); if(f1!=f2) field[f2]=f1; } int main() { //freopen("C:\\in.txt","r",stdin); while(cin>>N&&N) { cin>>M; memset(field,0,sizeof(field)); memset(degree,0,sizeof(degree)); while(M--) { cin>>a>>b; ++degree[a]; //a的度(出度)++ ++degree[b]; //b的度(入度)++ make(a,b);//将a b合并 } int cnt = 0; //集合的个数,等于1才满足欧拉回路 int flag = 1; for(int i=1;i<=N;++i) { if(field[i]==0) cnt++; if(degree[i]%2==1) flag=0; } if(cnt!=1) flag=0; cout<<flag<<endl; } return 0; } /************************************************************** Problem: 1027 User: starcuan Language: C++ Result: Accepted Time:130 ms Memory:1528 kb ****************************************************************/
原文:http://blog.csdn.net/starcuan/article/details/19302633