2337_eulerrd.cpp

pku 2337 欧拉路 北大ACM网站上的算法题

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <assert.h>
#include <string>
using namespace std;

#define min(a,b) ((a)<(b)?(a):(b))

#define MAXLEN 20
#define MAXSTRNUM 1000

struct String
{
	char str[MAXLEN+1];
	char len;
	bool operator <(const String& p)
	{//此处有歧义，azoha.arachnid谁在前面？
		int n=min(len,p.len)+1;//考虑长度不同的情况，比较\0
		for (int i=1;i<n;i++)
			if(str[i]!=p.str[i])
				return str[i]<p.str[i];
		return true;
	}
	void getlen()
	{
		len=0;
		while(str[len])len++;
	}
	int fst()
	{ return str[0]-'a';}
	int lst()
	{ return str[len-1]-'a';}
};

int T,N;
String buffer[MAXSTRNUM+1];
int memi;
struct Index
{
	int idx;
	bool vised;
	bool operator<(const Index& p)
	{ return buffer[idx]<buffer[p.idx];}
	char* operator ()()
	{ return buffer[idx].str;}
	Index(int _idx):idx(_idx){vised=false;}
	Index(){idx=-1;vised=false;}
	int fst()
	{ return buffer[idx].fst();}
	int lst()
	{ return buffer[idx].lst();}
};

vector<Index> graph[26];
int mark[26][26];//0为没有边，n为由n条边，-1为桥,此时必为一条边,-2为非桥且一条边
int indeg[26],outdeg[26];
vector<Index> ans;

bool dfs()
{//连通性测试
	int i;
	char flag[26]={0};
	int S[26];
	int top=-1;

	int s=-1,t=-1;
	for (i=0;i<26;i++)
	{
		if(outdeg[i]&&t==-1)
			t=i;
		if(outdeg[i]==indeg[i])
			continue;
		if(outdeg[i]==indeg[i]+1)
		{
			s=i;
			break;
		}
	}
	s=(s==-1?t:s);
	S[++top]=s;
	flag[s]=1;
	while (top!=-1)
	{
		int idx=S[top--];
		for (i=0;i<graph[idx].size();i++)
		{
			int nex=graph[idx][i].lst();
			if(!flag[nex])
			{
				S[++top]=nex;
				flag[nex]=1;
			}
		}
	}
	for (i=0;i<26;i++) if((indeg[i]||outdeg[i])&&!flag[i])
		return false;
	return true;
}
bool inoutcheck(int& s,int& e)
{
	s=-1,e=-1;
	for (int i=0;i<26;i++)
	{
		if(indeg[i]==outdeg[i])
		{
			continue;
		}
		if(indeg[i]>outdeg[i]+1||outdeg[i]>indeg[i]+1)
			return false;
		if(indeg[i]==outdeg[i]+1)
		{
			if(e!=-1)
				return false;
			e=i;
		}
		if(outdeg[i]==indeg[i]+1)
		{
			if(s!=-1)
				return false;
			s=i;
		}
	}
	return true;
}
bool check(int& s,int& e)
{
	return inoutcheck(s,e)&&dfs();
}
void Print()
{
	printf("%s",ans[0]());
	for (int i=1;i<ans.size();i++)
		printf(".%s",ans[i]());
	printf("\n");
}
int chkbridge(int s,int e)//为桥-1，否则-2
{//s，e为要去边的起点和终点,搜索去掉改变后是否存在从e到s的路径
	if(s==e) return -2;
	mark[s][e]=0;
	queue<int> Q;
	Q.push(e);
	bool flag[26]={0};
	flag[e]=1;
	while (!Q.empty())
	{
		int cur=Q.front();Q.pop();
		for (int i=0;i<26;i++)
		{
			if(mark[cur][i]&&!flag[i])
			{
				if(i==s) return -2;//非桥
				flag[i]=1;
				Q.push(i);
			}
		}
	}
	mark[s][e]=1;
	return -1;
}
bool Euler(int s,int n)
{
	int i;
	if(!outdeg[s])
	{
		if(n)
		{	/*ans.clear();printf("***\n");*/ return false;}
		Print();
		return true;
	}
	--outdeg[s];
	int fstbdgidx=-1;//第一个桥的下标
	for(i=0;i<graph[s].size();i++) if(!graph[s][i].vised)
	{
		if(mark[s][graph[s][i].lst()]==1)
			mark[s][graph[s][i].lst()]=chkbridge(s,graph[s][i].lst());
		if(mark[s][graph[s][i].lst()]==-1)
		{
			fstbdgidx=(fstbdgidx==-1?i:fstbdgidx);
			continue;
		}
		//非桥
		mark[s][graph[s][i].lst()]=
			(mark[s][graph[s][i].lst()]==-2?0:(mark[s][graph[s][i].lst()]-1));
		graph[s][i].vised=true;
		ans.push_back(graph[s][i]);
		return Euler(graph[s][i].lst(),n-1);
	}
	//走桥
	mark[s][graph[s][fstbdgidx].lst()]=0;
	graph[s][fstbdgidx].vised=true;
	ans.push_back(graph[s][fstbdgidx]);
	return Euler(graph[s][fstbdgidx].lst(),n-1);
}
void solve()
{
	int s,e;
	ans.clear();
	if(!check(s,e))
	{
		printf("***\n");
		return;
	}
	if(s!=-1)
		Euler(s,N);
	else
	{
		for (int i=0;i<26;i++) if (outdeg[i])
		{
			Euler(i,N);
			return;
		}
	}
}
//FILE* pf;
void init()
{
	int i;
	scanf("%d",&N);
	memi=0;
	memset(indeg,0,sizeof(indeg));
	memset(outdeg,0,sizeof(outdeg));
	memset(mark,0,sizeof(mark));
	for (i=0;i<26;i++)
	{ graph[i].clear();}
	for (i=0;i<N;i++)
	{
		scanf("%s",&buffer[memi]);
		buffer[memi].getlen();
		graph[buffer[memi].fst()].push_back(Index(memi));
		mark[buffer[memi].fst()][buffer[memi].lst()]++;
		++indeg[buffer[memi].lst()];++outdeg[buffer[memi].fst()];
		++memi;
	}
	for (i=0;i<26;i++)
		sort(graph[i].begin(),graph[i].end());
}
int main(int argc, char* argv[])
{
	scanf("%d",&T);
	for (int i=0;i<T;i++)
	{
		//////////////////////////////////////////////////////////////////////////
		init();
		solve();
		//////////////////////////////////////////////////////////////////////////
	}
	return 0;
}