codeforces 766 D. Mahmoud and a Dictionary（种类并查集+stl）
2024-09-01 05:55:15
题目链接：http://codeforces.com/contest/766/problem/D
题意：给你n个单词,m个关系(两个单词是反义词还是同义词)，然后问你所给的关系里面有没有错的，最后再给你q个询问,问你两个单词之间的关系是什么，
同义词输出1,反义词输出2,不确定输出3;
其实就是种类并查集。种类并查集怎么做之前的随笔中有说过。
#include <iostream>
#include <cstring>
#include <map>
using namespace std;
const int M = 1e5 + 10;
int f[M] , root[M] , n , m;
void init() {
for(int i = 1 ; i <= n ; i++) {
f[i] = i , root[i] = 0;
}
}
int find(int x) {
if(x == f[x])
return x;
int tmp = find(f[x]);
root[x] = (root[x] + root[f[x]]) % 2;
return f[x] = tmp;
}
string s , s1 , s2;
map<string , int>mmp;
int main() {
int x , y , num , q;
cin >> n >> m >> q;
init();
for(int i = 0 ; i < n ; i++) {
cin >> s;
mmp[s] = i + 1;
}
for(int i = 1 ; i <= m ; i++) {
cin >> num >> s1 >> s2;
x = mmp[s1] , y = mmp[s2];
int t1 = find(x) , t2 = find(y);
if(num == 1) {
if(t1 == t2) {
if(root[x] != root[y]) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
}
}
else {
cout << "YES" << endl;
f[t1] = t2;
root[t1] = root[y] - root[x];
root[t1] = (root[t1] + 2) % 2;
}
}
else {
if(t1 == t2) {
if(root[x] == root[y]) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
}
}
else {
cout << "YES" << endl;
f[t1] = t2;
root[t1] = (root[y] + 1 - root[x]);
root[t1] = (root[t1] + 2) % 2;
}
}
}
while(q--) {
cin >> s1 >> s2;
x = mmp[s1] , y = mmp[s2];
int t1 = find(x) , t2 = find(y);
if(t1 == t2) {
if(root[x] == root[y]) {
cout << 1 << endl;
}
else {
cout << 2 << endl;
}
}
else {
cout << 3 << endl;
}
}
return 0;
}
最新文章
- 旺财速啃H5框架之Bootstrap（五）
- SQL语句到底是怎么执行的
- SqlServer主键和外键
- 换个角度理解云计算之MapReduce
- [问题2014S14] 复旦高等代数II（13级）每周一题（第十四教学周）
- C++输入输出
- PHP学习笔记：万能随机字符串生成函数（已经封装好）
- [转]C++ string的trim, split方法
- Java凝视Override、Deprecated、SuppressWarnings具体解释
- Linux学习笔记2——Linux中常用文件目录操作命令
- 连接SQLServer ＯＬＥＤＢ数据库（ACCESS） ODBC Oracle
- IDAPython: importing “site” failed
- swift UILabel多行显示时 计算UILable的高度（可用于UILable高度自适应）
- webpack 代码优化压缩方法
- LR-SVM(有待重新整理)
- ssm+maven+pageHelper搭建maven项目实现快速分页
- Confluence 6 设置你的个人空间主页
- 解决Android adjustresize全屏无效问题
- springboot---数据整合篇
- Bootstrap源码解读之栅格化篇