單詞拼接——有向圖歐拉回路判斷

平時做有向圖歐拉回路的題時，我們都預設圖是弱連通的，但是今天這道題需要判斷。

傳送門

就是一道有向圖歐拉回路的判定，關鍵在于判斷圖是否連通，這裡我們用并查集來判斷圖是否連通。

/*
	有向圖判定歐拉回路，難點在于判斷圖是不是連通，利用并查集
*/
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int MAX_N = 1e5+5;
struct edge
{
	int v,next;
}e[MAX_N];
int p[MAX_N],eid;
void init()
{
	memset(p,-1,sizeof(p));
	eid = 0;
}
void insert(int u,int v)
{
	e[eid].v = v;
	e[eid].next = p[u];
	p[u] = eid++;
}
int n,degree[MAX_N];
void euler()
{
	int first = 0,last = 0;
	for(int i=1;i<=26;i++)
	{
		if(degree[i]<-1 || degree[i]>1)
		{
			cout<<"impossible"<<endl;
			return ;
		}
		else if(degree[i] == -1)
		{
			if(first != 0)
			{
				cout<<"impossible"<<endl;
				return ;
			}
			else
				first = i;
		}
		else if(degree[i] == 1)
		{
			if(last != 0)
			{
				cout<<"impossible"<<endl;
				return ;
			}
			else
			{
				last = i;
			}
		}
	}
	if(first == 0 && last == 0)
	{
		cout<<"Euler loop"<<endl;
	}
	else if(first != 0 && last != 0)
	{
		cout<<"Euler path"<<endl;
	}
}
//并查集部分，用來判斷圖是不是連通
int father[30];

int find(int x)
{
	int r = x;
	while(father[r] != r)
		r = father[r];
	int j, i=x;
	while(i!=r)		//路徑壓縮
	{
		j = father[i];		//在改變上級之前用臨時變量j記錄下它的值
		father[i] = r;		//把上級改為根節點
		i=j;
	}
	return r;
}

void join(int x,int y)		//判斷x,y是否連通
							/*如果已經連通，就不用管了 如果不連通，
							就把它們所在的連通分支合并起,*/
{
	int fx = find(x),fy=find(y);
	if(fx!=fy)
		father[fx]=fy;
}

bool vis[30];
int jilu[30],cnt = 0;
int main()
{
	for(int i=1;i<=26;i++)
		father[i] = i;		//初始化26個字母分别對應1-26個數，他們自己的父節點一上來都是自己
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int u,v;
		string s;
		cin>>s;
		u = s[0] - 'a' + 1;
		v = s[s.length()-1] - 'a' + 1;
		insert(u,v);
		degree[u]--;
		degree[v]++;
		if(!vis[u])
		{
			vis[u] = true;
			jilu[cnt++] = u;
		}
		if(!vis[v])
		{
			vis[v] = true;
			jilu[cnt++] = v;
		}
		join(u,v);
	}
	for(int i=0;i<cnt-1;i++)
	{
		if(find(jilu[i]) != find(jilu[i+1]))
		{
			cout<<"impossible"<<endl;
			return 0;
		}
	}
	euler();
	return 0;
}