1 条题解

  • 0
    @ 2026-6-12 9:07:44
    #include<bits/stdc++.h>
    #define pii array<int,2>
    using namespace std;
    int T,n,r[30],c[30],f[30],st,ed,lc;
    char ch[1005];
    vector<int>v[30];
    stack<int>ans;
    int fd(int x){
        if(x==f[x])return x;
        return f[x]=fd(f[x]);
    }
    bool solve(){
        for(int i=1;i<=26;i++){
            if(c[i]>r[i]+1||r[i]>c[i]+1)return 0;
            if(c[i]==r[i]+1){
                if(st)return 0;
                st=i;
            }
            if(r[i]==c[i]+1){
                if(ed)return 0;
                ed=i;
            }
            if(c[i]+r[i]){
                if(!lc)lc=fd(i);
                if(lc!=fd(i))return 0;
            }
        }
    
        return 1;
    }
    int main(){
        scanf("%d",&T);
        while(T--){
            scanf("%d",&n);
            for(int i=1;i<=26;i++)v[i].clear(),f[i]=i;
            memset(r,0,sizeof r);
            memset(c,0,sizeof c);
            st=ed=lc=0;
            for(int i=1;i<=n;i++){
                scanf("%s",ch+1);
                int len=strlen(ch+1),x=ch[1]-'a'+1,y=ch[len]-'a'+1;
                v[x].push_back(y);
                c[x]++;r[y]++;
                int fx=fd(x),fy=fd(y);
                if(fx!=fy)f[fx]=fy;
            }
            printf(solve()?"Ordering is possible.\n":"The door cannot be opened.\n");
        }
        return 0;
    }
    
    • 1

    信息

    ID
    1865
    时间
    1000ms
    内存
    32MiB
    难度
    10
    标签
    递交数
    7
    已通过
    2
    上传者