题目链接:DongDong认亲戚 (nowcoder.com)
在之前我写过一个并查集的题目,详见《【并查集】poj1611 – The Suspects – ErikTse Runtime》,这是一道用数字表示点的并查集模型,但是本题 DongDong认亲戚 是用字符串表示点的,其实换汤不换药,用一个map将字符串和编号联系起来就行了。
思路
并查集。
用一个map<string, int> s2i表示从string 指向 int。
我用了一下string的快速读入,让代码简洁了一些(疯狂压行),速度也更快。(cin读入真的挺慢的)
代码
/*Copyright (C) Eriktse 2022*/ #include <iostream> #include <cstdio> #include <stack> #include <queue> #include <cmath> #include <cstring> #include <string> #include <vector> #include <map> #include <algorithm> #include <bitset> #include <utility> #define fi first #define se second #define gc getchar #define pr printf #define sc scanf #define pb push_back #define int long long //用%lld输出long long类型数据 using namespace std; inline int readInt() { int s = 0,w = 1;char c = gc(); while(c < '0' || c > '9'){if(c == '-')w = -1;c = gc();} while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();} return s * w; } inline string readString() { string s;char c = gc(); while(c == '\n' || c == '\r' || c == ' ')c = gc(); while(c != '\n' && c != '\r' && c != ' '){s = s + c, c = gc();} return s ; } /*--------全局变量--------*/ const int maxn = 2e5 + 10; map<string, int> s2i; int pre[maxn]; /*--------自定义函数-------*/ inline int root(int x) { int rx = x; while(pre[rx] != rx)rx = pre[rx]; return pre[x] = rx; } signed main() { int N = readInt(), M = readInt(); for(int i = 1;i <= N; ++ i)pre[i] = s2i[readString()] = i; while(M --) { int op = readInt(); if(op == 1)pre[root(s2i[readString()])] = root(s2i[readString()]); else if(op == 2)pr("%d\n", root(s2i[readString()]) == root(s2i[readString()]) ? 1 : 0); } return 0; }
Comments NOTHING