ZOOM笔试股票推荐，带树重量的查并集，输入输出写的很菜
#include <iostream>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
template<class T>
class UF{
private:
int m_cnt;
unordered_map<T,T> parent;
unordered_map<T,int> size;
public:
UF(){};
void connect(T p,T q)
{
T rootp=find(p);
T rootq=find(q);
if(rootp==rootq) return;
parent[rootq]=rootp;
size[rootp]+=size[rootq];
--m_cnt;
}
void insert(T key){
if(parent.count(key)) return;
parent[key]=key;
size[key]=1;
++m_cnt;
}
T find(T x){
//找到根节点
if(x!=parent[x]){
parent[x]= find(parent[x]);
}
return parent[x];
}
bool connected(T p,T q){
T rootp=find(p);
T rootq=find(q);
return rootp==rootq;
}
int count(){
return m_cnt;
}
int getSize(T q){
T rootq= find(q);
return size[rootq];
}
};
unordered_map<string,unordered_set<string>> people2com;
UF<string> uf;
void insertPeople(string s1,string s2){
stringstream ss1(s1);
stringstream coms(s2);
vector<string> person;
vector<string> companys;
string tmp;
while(ss1>>tmp) person.push_back(tmp);
string p=person[1];
while(coms>>tmp){
//保存这个人关注的公司
people2com[p].insert(tmp);
uf.insert(tmp);
}
auto it=people2com[p].begin();
string root=*it;
++it;
while(it!=people2com[p].end()){
//跟第一个公司相连接
uf.connect(root,*it);
++it;
}
}
int getCnt(string s1){
int ret=0;
stringstream ss1(s1);
string tmp;
vector<string> person;
while(ss1>>tmp) person.push_back(tmp);
string p=person[1];
if(people2com.count(p)){
int size=people2com[p].size();
ret=uf.getSize(*people2com[p].begin());
ret-=size;
}else{
ret=-1;
}
return ret;
}
int main(){
string n;
getline(cin,n);
for(int i=0;i< stoi(n);++i){
string work;
getline(cin,work);
if(work[0]=='1'){
string companys;
getline(cin,companys);
insertPeople(work,companys);
}else{
int ret=getCnt(work);
if(ret<0) cout<<"error"<<endl;
else cout<<ret<<endl;
}
}
} #Zoom#
