首页 > 代码库 > UVa10129,Play On Words

UVa10129,Play On Words

2024-07-14 10:15:54   219人阅读

给出n个单词，如果一个单词的尾和另一个单词的头字符相等，那么可以相连，问这n个单词是否可以排成一列。欧拉路应用，构图：一个单词的头尾字母分别作为顶点，每输入一个word，该word的头指向word的尾画一个有向边，并且记录每个顶点的出入度。利用dfs先判断是否为一个连通图，如果是的话则判断是否有且仅有一个起点和终点（abs（出度-入度）=1），或是一个环

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <algorithm>#include <cmath>#define maxn 100000+5using namespace std;string map[maxn];int n,chu[30],ru[30],G[30][30],vst[30],f,ok,c[30],cnt,ts;int init(){    cin>>n;    memset(chu,0,sizeof(chu));    memset(ru,0,sizeof(ru));    memset(G,0,sizeof(G));    memset(vst,0,sizeof(vst));    memset(c,0,sizeof(c));    cnt=0;    string temp;    for (int i=0;i<n;i++){        cin>>map[i];        int p,q;        p=map[i][0]-‘a‘;        q=map[i][map[i].size()-1]-‘a‘;        ts=p;        if (!c[p]) {cnt++;c[p]=1;}        if (!c[q]) {cnt++;c[q]=1;}        G[p][q]=1;        chu[p]++;ru[q]++;    }    }int is_link(int p){    for (int j=0;j<30;j++){        if (G[p][j]&&!vst[j]){            vst[j]=1;            f++;            is_link(j);        }    }}int find_start(){    int i;    for ( i=0;i<30;i++)        if (chu[i]-ru[i]==1) return i;    if (i==30) return ts;    //cout<<"find"<<ok<<endl;}int work(){    int t=0,f=0;    for (int i=0;i<30;i++)                    if (chu[i]!=ru[i]){                if (abs(chu[i]-ru[i])==1)t++;                else f=1;            }    if ((t==0&&f==0)||(t==2)) return 1;    return 0;}int main(){    int T;    cin>>T;    while (T--){        init();        ok=1;        int p;        p=find_start();        vst[p]=1;        f=1;        if (ok)is_link(p);        if (f!=cnt) ok=0;        if (ok) ok=work();        if (ok) cout<<"Ordering is possible."<<endl;        else cout<<"The door cannot be opened."<<endl;    }}
View Code

 


联系
我们