错哪了,求条
查看原帖
错哪了,求条
1501877
wuzebang2009楼主2025/1/22 18:37
#include<bits/stdc++.h>
using namespace std;
const int N=30;
// vector<int> ver[N];
int t,n,ind[N],oud[N];
int fa[110],vis[N];

int find(int x){
    if(x==fa[x]) return fa[x]=x;
    fa[x]=find(fa[x]);
    return fa[x];
}

int main(){
    cin>>t;
    while(t--){
        cin>>n;
        // for(int i=1;i<=26;i++) ver[i].clear();
        memset(ind,0,sizeof ind);
        memset(oud,0,sizeof oud);
        memset(vis,0,sizeof vis);
        for(int i=1;i<=66;i++){
            fa[i]=i;
        }
        for(int i=1;i<=n;i++){
            string x;
            cin>>x;
            int a=x[0]-'a'+1,b=x[x.size()-1]-'a'+1;
            vis[a]=vis[b]=1;
            fa[find(b)]=find(a);
            // ver[a].push_back(b);
            oud[a]++;
            ind[b]++;
        }
        int cnt=0;
        for(int i=1;i<=26;i++){
            if(fa[i]==i && vis[i]) cnt++;
        }
        if(cnt>1){
            cout<<"The door cannot be opened.";
            if(t) puts("");
            continue;
        }
        // for(int i=1;i<=26;i++){
		//     sort(ver[i].begin(),ver[i].end());
	    // }
        int flag=1;
        bool ok=1;
        // int start;
        int sum1=0,sum2=0;//起点和终点数
        for(int i=1;i<=26;i++){
            if(!vis[i]) continue;
            if(ind[i]!=oud[i]){
                flag=0;
            }
            if(abs(ind[i]-oud[i])>1){
                // cout<<"The door cannot be opened.";
                ok=0;
                break;
            }
            if(oud[i]-ind[i]==1){
                // start=i;
                sum1++;
            }
            if(ind[i]-oud[i]==1){
                sum2++;
            }
        }
        if(!ok){
            cout<<"The door cannot be opened.";
        }
        else{
            if(!(flag==1||((sum1==sum2)&&sum1==1))){
                cout<<"The door cannot be opened.";
            }
            else{
                cout<<"Ordering is possible.";
            }
        }
        if(t) puts("");
    }
}
2025/1/22 18:37
加载中...