程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 2337 Catenyms (邊最小字典序歐拉路徑 Fleury)

poj 2337 Catenyms (邊最小字典序歐拉路徑 Fleury)

編輯:C++入門知識

題目鏈接: poj 2337

題目大意: 給出N個單詞,單詞A的開頭與另外單詞B結尾相同

則單詞A和單詞B可以連起來,問是否可以把所有單詞都串成一條線

輸出最小字典序的(按單詞的字典序串)

解題思路: 對於每個單詞,把單詞的起點和終點字母當作頂點

這個單詞即是起點到終點的一條單向邊

根據有向圖的歐拉圖判斷,若頂點的出度-入度為0,或者一個為1一個為-1則是歐拉通路

根據題意還可能是不連通的圖,所以最後在判斷一下是否是聯通圖

PS:歐拉路徑的問題要記得判斷圖是否聯通

代碼:

#include 
#include 
#include 
#include 
#define MAX 2010
#define INF 0x3f3f3f
using namespace std;
int k,Index,visit[MAX],pre[50],In[50],To[50],ans[MAX];
struct snode{
	int len;
	char ch[25];
}num[MAX];
struct node{
	int to,next,w;
}edge[MAX<<3];

void Add_edge(int a,int b,int w)
{
	edge[Index].to=b;
	edge[Index].w=w;
	edge[Index].next=pre[a];
	pre[a]=Index++;
}

bool cmp(struct snode a,struct snode b)
{
    if(strcmp(a.ch,b.ch)>=0)
        return false;
    return true;
}

void Fleury(int start)
{
	int i,v;
	for(i=pre[start];i!=-1;i=edge[i].next)
	{
		v=edge[i].to;
		if(!visit[edge[i].w])
		{
			visit[edge[i].w]=1;
			Fleury(v);
			ans[++k]=edge[i].w; //記錄邊的訪問順序
		}
	}
}

int main()
{
	char ch1[25];
	int t,i,j,n,m,a,b,pd,pd1,pd2,start;
	scanf("%d",&t);
	while(t--)
	{
		Index=pd1=pd2=k=0;
		memset(visit,0,sizeof(visit));
		memset(pre,-1,sizeof(pre));
		memset(num,0,sizeof(num));
		memset(In,0,sizeof(In));
		memset(To,0,sizeof(To));
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		{
			scanf("%s",num[i].ch);
			num[i].len=strlen(num[i].ch);
		}
		sort(num+1,num+1+n,cmp);
		start=INF;
		for(i=n;i>=1;i--)
		{
			a=num[i].ch[0]-'a'+1;
			b=num[i].ch[num[i].len-1]-'a'+1;
			Add_edge(a,b,i);
			To[a]++,In[b]++;
			if(start>a)
				start=a;
			if(start>b)
				start=b;
		}
		m=-1;
		for(i=1;i<=26;i++)
		{
			if(To[i]-In[i]==1)
			{
				if(m==-1)
					m=i;
				pd1++;
			}
			else if(To[i]-In[i]==-1)
                pd2++;
            else if(To[i]!=In[i])
            {
                pd1=3;
                break;
            }
		}
		if(pd1==1&&pd2==1)    //若出度-入度之差為1和-1的點各有一個,起點是值1的
		    start=m;
		else if(pd1==0&&pd2==0)  //不存在則選序號最小的頂點
			start=start;
		else
        {
            printf("***\n");
			continue;
        }
		Fleury(start);
		if(k!=n)       //判斷圖是否聯通
		{
			printf("***\n");
			continue;
		}
		for(i=k;i>=1;i--)
		{
			printf("%s%c",num[ans[i]].ch,".\n"[i==1]);
		}
	}
	return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved