【例题 6-16 UVa 10129】Play on Words
On 16 UVa words 例题 Play
2023-09-14 09:03:45 时间
【链接】 我是链接,点我呀:)
【题意】
【题解】
入度减去出度个数为1的点和为-1的点各有1个,然后其他点入度减去出度为0 或者全都是入度为0的点即可。【代码】
#include <bits/stdc++.h>
using namespace std;
const int N = 300;
int n,du[N];
map <char,int> mmap;
int f[N+10];
bool bo[N+10];
int ff(int x){
if (f[x]==x) return x;
else return f[x] = ff(f[x]);
}
int main(){
#ifdef LOCAL_DEFINE
freopen("F:\\c++source\\rush_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
int T;
cin >> T;
while (T--){
memset(du,0,sizeof du);
memset(bo,0,sizeof bo);
for (int i = 'a';i <= 'z';i++)
f[i] = i;
cin >> n;
string s;
for (int i = 1;i <=n;i++){
cin >> s;
int x = s[0],y = s[(int) s.size()-1];
du[(int) s[0]]++;
du[(int) s[(int) s.size()-1]]--;
bo[(int) s[0]] = true;
bo[(int) s[(int) s.size()-1]] = true;
if (ff(x)!=ff(y)){
f[ff(x)] = ff(y);
}
}
bool ok = true;
int idx = 'a';
for (int i = 'a';i <= 'z';i++)
if (bo[i]){
idx = ff(i);
}
for (int i = 'a';i <= 'z';i++)
if (bo[i]&& ff(i)!=idx)
ok = false;
if (!ok){
cout <<"The door cannot be opened."<<endl;
continue;
}
int fi1 = 0,fi2 = 0;
for (int i = 'a';i <= 'z';i++)
if (du[i]==-1)
fi1++;
else if (du[i]==1){
fi2++;
}else if (du[i]!=0) fi1 = 2;
if ((fi1==1 && fi2==1) || (fi1==0 && fi2==0)){
cout << "Ordering is possible." << endl;
}else cout <<"The door cannot be opened."<<endl;
}
return 0;
}
相关文章
- github开发人员在七夕搞事情:remote: Support for password authentication was removed on August 13, 2021.
- Sounds Identification on CM7
- Hands on Reinforcement Learning 05 Temporal Difference
- ORA-22804: remote operations not permitted on object tables or user-defined type columns ORACLE 报错 故障修复 远程处理
- ORA-25201: invalid value, VISIBILITY should be ON_COMMIT or IMMEDIATE ORACLE 报错 故障修复 远程处理
- ORA-27612: Smart I/O failed due to a block corruption detected on the cell “string”. disk: “string”, block: “string”, disk offset: “string” ORACLE 报错 故障修复 远程处理
- ORA-38713: Flashback Database logging is already turned on. ORACLE 报错 故障修复 远程处理
- ORA-38722: ON or OFF expected. ORACLE 报错 故障修复 远程处理
- ORA-02825: Request on free list was not free ORACLE 报错 故障修复 远程处理
- ORA-03251: Cannot issue this command on SYSTEM tablespace ORACLE 报错 故障修复 远程处理
- MySQL Error number: MY-011540; Symbol: ER_GRP_RPL_SLAVE_SQL_THD_ON_SECONDARY_MEMBER; SQLSTATE: HY000 报错 故障修复 远程处理
- ORA-12032: cannot use rowid column from materialized view log on “string”.”string” ORACLE 报错 故障修复 远程处理
- ORA-12854: Parallel query is not supported on temporary LOBs ORACLE 报错 故障修复 远程处理
- jquery关于on click事件的理解详解编程语言
- MySQL 中的 ON 含义及应用场景解析(mysql中on什么意思)