CF 288DIV2 D - Tanya and Password (弗罗莱算法求欧拉通路)

旭哥的弗罗莱讲解

http://www.cnblogs.com/Lyush/archive/2013/04/22/3036659.html

有关欧拉通路的定理：

http://wenku.baidu.com/link?url=bPYyQ14FoKm31UFCR-iOO00-V4iBMc4XPlboBTtKskUG5Lj7BbgWsL62NX7TtZ0BhgsExjPN9UfqBw3bv9t6O-D514qhhvTSduUuZB5AWvS

自己的一些理解：

定理：无向图中，无向图G存在欧拉通路 <==> G是连通的且有0个或2个奇数度点

在0个奇术度点，起点v0为任意一点，在2个奇术度点时，起点v0为某个奇数度点，找出一个通路P= v0e1v1e2v2..ekvk . 若P经过了图G的所有边，则P是欧拉通路，否则通道P中必然与图G'= G-｛v0,v1,v2...vk｝有交点，且图G'都是度数为偶数的点，所以我们可以用交点在G'中找出通路P1,P2,P3,P4,。。。将这些通路组合到一起就是欧拉通路

定理：有向图G中存在欧拉通路 <==> G是联通的，所有点出度和入度相等或者有两个点，一个出度比入度多1，一个入度比出度多1，其他点出度和入度相等

有向图同理

自己总结的结论：若无向图存在0个或2个奇数点但不存在欧拉通路，则图G不连通且是多个存在欧拉通路的子图形成

所有点出度和入度相等或者有两个点，一个出度比入度多1，一个入度比出度多1，其他点出度和入度相等，但不存在欧拉通路，则图G不连通且是多个存在欧拉通路的子图形成

使用改算法时，遍历每一条边之后都删除改边会加快效率

题意：

给你n个字符串（长度均为3），一个字符串的后两个字符和另一个字符串前两个字符相同的话可以连接，例如abc和bcd可以连接成字符串abcd,求n个字符串全部连接后形成的字符串

方法：

把字符串abc看成点ab-->bc的一条边，求图的欧陆通路即可

写代码遇到的问题：

遍历边之后没删除边 TLE过

代码：

#include <cstdio>
#include <cstring>

#define maxm 200010
#define maxn 4000

struct node
{
	int v, next;
}edge[maxm];

int head[maxn], hash[maxm];
int in[maxn], out[maxn];
int s[maxm], ss= 0;
int ans[maxm],tot= 0;
int n;
int start;//start表示欧拉通路的起点 
int deal(char ch)
{
	if(ch>= 'a' && ch<= 'z')
		return ch-'a'+1;
	if(ch>= 'A' && ch<= 'Z')
		return ch-'A'+27;
	if(ch>='0' && ch<= '9')
		return ch-'0'+ 53;		
}

char Deal(int x)
{
	if(x>= 1 && x<= 26)
		return 'a' + x- 1;
	if(x>= 27 && x<= 52)
		return 'A'+ x- 27;
	if(x>= 53 && x<= 62)
		return '0'+ x- 53;		
}

void add(int x, int y, int tot)
{
	edge[tot].v= y;
	edge[tot].next= head[x];
	head[x]= tot;
}

void dfs(int x)
{
	for(int i= head[x]; i!= -1; i= edge[i].next)
		if(!hash[i])
		{
			hash[i]= 1;
			head[x]= edge[i].next; //此处删边是防TLE 
			s[++ss]= edge[i].v;
			dfs(edge[i].v);
			break;
		}
}

void Fleury(int x)
{
	ss= 0, tot= 0;
	s[++ss]= x;
	int y= x;
	while(ss> 0)
	{
		int flag= 0;//表示s[ss]是否为欧拉通路与剩下的图G'的交点 
		for(int i= head[s[ss]]; i!= -1; i= edge[i].next)
			if(!hash[i])
			{
				flag= 1;
				break;
			}		
		if(flag== 0)
		{
			ans[++tot]= s[ss];
			ss--;
		}
		else
			dfs(s[ss]);	
	}
	if(tot!= n+1) //可能图G是由两个或多个存在欧拉通路的互不连通图形成的 
	{
		printf("NO\n");
	}
	else
	{
		printf("YES\n");
		for(int i= tot; i>= 1; i--)
			printf("%c",Deal(ans[i]/63));
		printf("%c\n",Deal(ans[1]%63));	
	}	
}

int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		char ch[10];
		memset(out, 0, sizeof out);
		memset(in,0, sizeof in);
		memset(head, -1, sizeof head);
		memset(hash, 0, sizeof hash);
		
		
		for(int i= 1; i<= n; i++)
		{
			scanf("%s",ch);
			int x= deal(ch[0])*63+ deal(ch[1]);
			int y= deal(ch[1])*63+ deal(ch[2]);
			add(x, y, i);
			out[x]++;
			in[y]++;
			start= x;
		}
		int s1= 0, s2= 0, s3= 0;//s1表示出度比入度大1的点数目，s2表示出度=入度，s3表示入度=出度+1 
		for(int i= 1; i< 4000; i++)
			if(out[i]== in[i]+ 1)
			{
				start= i;
				s1++;
			}
			else if(out[i]== in[i])
				s2++;
			else if(in[i]== out[i]+ 1)	
				s3++;	
		if(s1+ s2 +s3 != 3999 || (s1> 1) || s3> 1 || (s1^s3))
		{
			printf("NO\n");
			continue;
		}
		Fleury(start);
	}
	return 0;	
}

秒客网

CF 288DIV2 D - Tanya and Password (弗罗莱算法求欧拉通路)

相关文章