1388：家谱(gen)(并查集+字符串处理)

1388：家谱(gen)

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 4704     通过数: 2415

【题目描述】

【输入】

【输出】

【输入样例】

#George
+Rodney
#Arthur
+Gareth
+Walter
#Gareth
+Edward
?Edward
?Walter
?Rodney
?Arthur
$

【输出样例】

Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur

思路：

直接无脑跟题目模拟，用一个vec数组存储曾经出现过的人,输入一个人名s后先用一个临时string tk存储s,再删掉第一个操作字符(只保留剩下的人名)后在vec中查找tk以前有没有出现,如果没有则将fa[tk] = tk(fa是一个map),如果有则不需要做上述操作,然后判断s[0]是否为'?',是则将s的第一位删除再输出s和fin(s)，如果s[0]=='#'则将将s的第一位删除再将f = s,否则说明s[0]为‘+'，则删除s[0],再join(s,f)即可。

#include <bits/stdc++.h>
using namespace std;
map<string,string>fa;
string s,f,tk;
char c;
vector<string>vec;
string fin(string k)
{
if(k == fa[k]) return k;
return fin(fa[k]);
}
void join(string p,string q)
{
string fp = fin(p),fq = fin(q);
if(fp != fq) fa[fp] = fq;
}
int main()
{
while(cin>>s)
{
tk = s;
tk.erase(0,1);
bool kj = 1;
for(int i = 0; i < vec.size(); i++)
if(vec[i] == tk)
kj = 0;
if(kj == 1)
{
fa[tk] = tk;
vec.push_back(tk);
}
if(s[0] == '$') break;
if(s[0] == '?')
{
s.erase(0,1);
cout<<s<<" "<<fin(s)<<endl;
}
else if(s[0] == '#')
{
s.erase(0,1);
f = s;
}
else if(s[0] == '+')
{
s.erase(0,1);
join(s,f);
}
//for(auto i:fa) cout<<i.first<<"_"<<i.second<<" ";
//cout<<endl;
}
return 0;
}

最后

以上就是怕孤独铅笔为你收集整理的1388：家谱(gen)(并查集+字符串处理)的全部内容，希望文章能够帮你解决1388：家谱(gen)(并查集+字符串处理)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。