首页 > 搜索 > DFS搜索 > HDU 1878 欧拉回路-DFS-[解题报告] C++
2013
12-23

HDU 1878 欧拉回路-DFS-[解题报告] C++

欧拉回路

问题描述 :

欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个图,问是否存在欧拉回路?

输入:

测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是节点数N ( 1 < N < 1000 )和边数M;随后的M行对应M条边,每行给出一对正整数,分别是该条边直接连通的两个节点的编号(节点从1到N编号)。当N为0时输入结
束。

输出:

每个测试用例的输出占一行,若欧拉回路存在则输出1,否则输出0。

样例输入:

3 3
1 2
1 3
2 3
3 2
1 2
2 3
0

样例输出:

1
0

//ashione 2011-6-1 ,欧拉回路检测
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define SetMax 1001
int in[SetMax],out[SetMax],map[SetMax][SetMax];
bool mark[SetMax];
void init(int n){
	memset(mark,false,(n+1)*sizeof(bool));
	memset(map,0,sizeof(map));
	memset(in,0,(n+1)*sizeof(int));
	memset(out,0,(n+1)*sizeof(int));
}
void dfs(int k,int n){//DFS寻找最大连通分量
	mark[k]=true;
	for(int i=1;i<=n;i++)
		if(map[k][i] && !mark[i]){
			dfs(i,n);
			break;
		}	
}
int main(){
	int n,m,a,b,i,j;
	while(cin>>n && n){
		cin>>m;
		init(n);
		while(m--){
			scanf("%d %d",&a,&b);
			map[a][b]=map[b][a]=1;
			out[a]++,in[b]++;//无向图入度与出度
			in[a]++,out[b]++;
		}
		dfs(1,n);		
		for(i=1;i<=n;i++)
			if(out[i]!=in[i] || !mark[i] || in[i]%2==1 )//当节点入度不等于出度或者连通分量大于1或者为奇数入度则不为欧拉回路
				break;
		puts((i==n+1)?"1":"0");
	}			
	return 0;
}

解题报告转自:http://blog.csdn.net/a342374071/article/details/6460232


,
  1. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  2. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts