本文共 2029 字,大约阅读时间需要 6 分钟。
3 31 21 32 33 21 22 30
10
一上来我直接用递归暴搜,结果超时:
#include所以,得从欧拉回路的性质出发,#include #include #define MAX 1005int 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
1、欧拉回路必须能从1一直能连线到n的连通图,所以用并查集的话,就只能有1个集合
2、欧拉回路:
有向图:所有的顶点出度=入度。
无向图:所有顶点都是偶数度。
满足上面两个条件的话就一定是欧拉回路
所以,利用并查集和节点度数的奇偶判断就可知是否是欧拉回路
/*题目1027:欧拉回路 */#include#include 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< <
转载地址:http://gdvvi.baihongyu.com/