1116.cpp

来自「杭电 acm部分代码 有兴趣的可以下载 谢谢」· C++ 代码 · 共 72 行

#include<stdio.h>
#include<string>
int vertex[27][27];
int have[27];
int connect[27];
int outdegree[27];
int indegree[27];
int dfs(int k){
    int j;
    connect[k]=1;
    for(j=0;j<26;j++)
        if((vertex[j][k]||vertex[k][j])&&(connect[j]==0))
            dfs(j);
}
int connection(){
    int i;
    for(i=0;i<26;i++)
        if(have[i]==1)
            break;
    dfs(i);
    for(i=0;i<26;i++)
        if(have[i]!=connect[i])
            return 0;
    return  1;
}
int degree(){
    int out=0,in=0;
    int i;
    for(i=0;i<26;i++){
        if(have[i]==1){
            if(outdegree[i]-indegree[i]==1)
                out++;
            else if(indegree[i]-outdegree[i]==1)
                in++;
            else if(indegree[i]-outdegree[i]>1||indegree[i]-outdegree[i]<-1)
                return 0;
        }
    }
    if((out==1&&in==1)||(out==0&&in==0))
        return 1;
    return 0;
}
int main()
{
    int tst,n,i;
    char str[1001];
    scanf("%d",&tst);
    while(tst--){
        scanf("%d",&n);
        memset(vertex,0,sizeof(vertex));
        memset(have,0,sizeof(have));
        memset(connect,0,sizeof(connect));
        memset(outdegree,0,sizeof(outdegree));
        memset(indegree,0,sizeof(indegree));
        while(n--){
            scanf("%s",str);
            int len=strlen(str);
            have[str[0]-'a']=have[str[len-1]-'a']=1;
            if(str[0]==str[len-1])
                continue;
            vertex[str[0]-'a'][str[len-1]-'a']++;
            outdegree[str[0]-'a']++;
            indegree[str[len-1]-'a']++;
        }
        if(connection()&&degree())
            printf("Ordering is possible.\n");
        else
            printf("The door cannot be opened.\n");
    }
    return 0;
}