http://acm.pku.edu.cn/JudgeOnline/problem?id=1386
這個(gè)題題意是給你一組單詞，要判斷是否能夠構(gòu)成一個(gè)
首尾相接的單詞鏈，例如給出如下單詞:
3
acm
malform
mouse
就可以構(gòu)成 acm->malform->mous的單詞鏈。
這種題實(shí)際上就是判斷有向圖的歐拉路的存在性。
也就是對(duì)所給的所有單詞，所有出現(xiàn)過(guò)的不同的字母就是圖上
的頂點(diǎn)，讀入每一個(gè)單詞，單詞的首字母對(duì)應(yīng)的點(diǎn)出度加1，末
字母對(duì)應(yīng)的點(diǎn)入度加1，最后再來(lái)做判斷。
最后構(gòu)成的鏈一定是這樣的:
對(duì)于上例就是：a->m->m->m->e;也就是所有字母對(duì)應(yīng)的入度等于出度
或是除了端點(diǎn)的字母各自的出入度相差一以外其余的出度入度都相等，
就滿足條件，能構(gòu)成鏈。
那么對(duì)于所有出現(xiàn)過(guò)的字母，只用判斷只有一個(gè)的出度為入度加1而
且只有一個(gè)的入度等于出度加1(如上例)，或所有點(diǎn)的出度等于入度
就可以了。當(dāng)然首先圖必須是連通的，這點(diǎn)很關(guān)鍵，這個(gè)可以用并查
集來(lái)做。這樣這題其實(shí)就很簡(jiǎn)單了。
poj還有個(gè)2337也是類似的題，不過(guò)那個(gè)題還需要把最后的歐拉路找
出來(lái)。http://acm.pku.edu.cn/JudgeOnline/problem?id=2337
code：
Source Code
| Problem: 1386 |
|
User: lovecanon |
| Memory: 208K |
|
Time: 313MS |
| Language: C++ |
|
Result: Accepted |
#include<stdio.h>
#include<string.h>
struct node{
int in,out;
}degree[26];
int father[26],rank[26],mem[27],vis[26],top;
int find(int t){
int tmp=t;
while(father[tmp]!=tmp) tmp=father[tmp];
father[t]=tmp;
return tmp;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int i,n;
char buf[1001];
scanf("%d",&n);
for(i=0;i<26;i++) {father[i]=i;rank[i]=0;}
memset(degree,0,sizeof(degree));
memset(vis,0,sizeof(vis));
top=0;
for(i=0;i<n;i++){
scanf("%s",buf);
int a=buf[0]-'a',b=buf[strlen(buf)-1]-'a';
if(!vis[a]) {vis[a]=1;mem[++top]=a;}
if(!vis[b]) {vis[b]=1;mem[++top]=b;}
degree[a].out++;degree[b].in++;
a=find(a);b=find(b);
if(a!=b){
if(rank[a]<rank[b]) father[a]=b;
else{
father[b]=a;
if(rank[a]==rank[b]) rank[a]++;
}
}
}
int tmp=find(mem[1]),flag=0;
for(i=2;i<=top;i++) if(find(mem[i])!=tmp) {flag=1;break;}
if(flag) {printf("The door cannot be opened.\n");continue;}
int sum=0,flag1=0,flag2=0,ok=1;
for(i=1;i<=top && sum<=2 && ok;i++){
if(degree[mem[i]].in!=degree[mem[i]].out){
sum++;
if(degree[mem[i]].in==degree[mem[i]].out+1) flag1++;
else if(degree[mem[i]].out==degree[mem[i]].in+1) flag2++;
else ok=0;
}
}
if(ok){
if(flag1==1&&flag2==1 || flag1==0&&flag2==0) printf("Ordering is possible.\n");
else printf("The door cannot be opened.\n");
}
else printf("The door cannot be opened.\n");
}
//system("pause");
return 0;
}