hdu1116--解题报告--初步了解欧拉回路

由题目意思..我们只要把n个字符串的首尾字母看作是点，这个字符串看着边来处理就可以啦...将题目的案例图形化如下：

那么接着就是欧拉路径和欧拉回路判断，我们这里用并査集来判断图是不是连通的，然后根据有向图的欧拉通路来判断：

欧拉通路：一个有向图当且仅当其实连通的，除了两个特例顶点之外，其他点的入度等于出度，这两个特例顶点是一个的入度-出度=1，一个的出度-入度=1;

上马：附加详细说明

// 250MS 264K

#include<cstdio>

#include<string>

#include<iostream>

using namespace std;

int in[27],out[27];//记录入度出度

int father[27];//并査集的父亲节点

string str;//每次要输入的字符串..这里定义全局，是为了判断连通图中有一个操作

int find(int a)

{

	if(a!=father[a])

		father[a]=find(father[a]);

	return father[a];

}

bool liantong()//连通

{

	int e=find(str[0]-'a');//根据最后输入的字符串的首字母去查是不是连通

	for(int i=0;i<26;i++)

		if((in[i] || out[i]) && find(i)!=e)//有这个点，并且如果不连通就返回false

			return false;

	return true;

}

bool huilu()//欧拉路径与回路的判断

{

	int k=0,kk=0;//k记录的是两个入度和出度相差一的个数，kk是记录入度等于出度的个数

	int flag=0;//图中顶点的个数

	for(int j=0;j<26;j++)

		if(in[j] != 0 || out[j] != 0)

			flag++;

	for(int i=0;i<26;i++)

	{

		if(in[i] == out[i] && in[i] != 0)

			kk++;

		else if(in[i]-out[i] == 1 || out[i]-in[i] == 1)

			k++;

	}

	if((k==2 && kk+k==flag) || kk==flag)//当有一个入度-出度=1和一个出度-入度=1并且其他点入度等于出度的就是一个欧拉路径，但是

		                               //还有可能所有的点的入度等于出度...那就是一个回路。一个环

		return true;

	return false;

}

int main()

{

	int T;

	int n;//n个字符串

	scanf("%d",&T);

	while(T--)

	{

		//init

		for(int i=0;i<27;i++) father[i]=i;

		memset(in,0,sizeof(in));

		memset(out,0,sizeof(out));

		scanf("%d",&n);

		while(n--)

		{

			cin>>str;

			int a=str[0]-'a',b=str[str.size()-1]-'a';

			out[a]++;

			in[b]++;

			father[find(a)]=find(b);

		}

		if(liantong() && huilu())

			printf("Ordering is possible.\n");

		else

			printf("The door cannot be opened.\n");

	}

	return 0;

}

ps:南阳42  一笔画问题也比较是和初步入门欧拉路的人