欣赏艺术类的网站,海南百度推广公司,wordpress商城 小程序,信息门户网站建设报价题目链接#xff1a;P2814 家谱 - 洛谷 | 计算机科学教育新生态
题目难度#xff1a;普及/提高 解题心得#xff1a;这道题用了并查集#xff08;貌似不怎么常用的字符串并查集#xff09;#xff0c;用STL中的map将子孙和祖先连接起来#xff0c;第一次接触这种做法感…题目链接P2814 家谱 - 洛谷 | 计算机科学教育新生态
题目难度普及/提高 解题心得这道题用了并查集貌似不怎么常用的字符串并查集用STL中的map将子孙和祖先连接起来第一次接触这种做法感觉很妙发篇题解记录下。。。。 代码部分
#includebits/stdc.h
using namespace std;
#define _for(i,a,b) for(int i(a); i(b); i)
#define _rep(i,a,b) for(int i(a); i(b); i)
typedef long long ll;
const int N 1e5 10;
mapstring,stringp;
string s,t;string find(string x)
{if(x ! p[x]) p[x] find(p[x]);return p[x];
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);char ch;cin ch;while(ch ! $){cin s;if(ch #){t s;if(p[s] ) p[s] s;}else if(ch ){p[s] t;}else couts find(s)\n;cin ch;} return 0;
}