1 条题解
-
0
#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
- 上传者