2562. Virtual Friends

GreyKa

并查集+STLmap

include

using namespace std;
map sett;
map ssize;
string get(string x){
if(sett[x]==x)return x;
return sett[x]=get(sett[x]);
}
void addP(string s){
if(sett.find(s)==sett.end())
sett[s]=s,ssize[s]++;
}
int main(){
int T;
cin>>T;
while(T–){
sett.clear(),ssize.clear();
int n;
cin>>n;
while(n–){
string s1,s2;
cin>>s1>>s2;
addP(s1),addP(s2);
if(get(s1)!=get(s2))
ssize[get(s2)]+=ssize[get(s1)],sett[get(s1)]=get(s2);
cout<<ssize[get(s2)]<<endl;
}
}
}

10152130255

百度到的让cin加速的 ios::sync_with_stdio(false)一用就wrong answer?
可以用,不过不能C和C++风格输入输出混用了。

10152130123

没用height也ac了??
一脸懵逼

Kevin_K

一个”just”引发的血案.gif

10152130146

百度到的让cin加速的 ios::sync_with_stdio(false)一用就wrong answer?
看来还是要scanf,这道题cin也来得及

LzQuarter
#include<iostream>
#include<map>
using namespace std;
int arr[200001];
int ctr[200001];
int ifind(int x){
    if(arr[x] != x){
        arr[x] = ifind(arr[x]);
    }
    return arr[x];
}
int ijoin(int a, int b){
    a = ifind(a);
    b = ifind(b);
    if(a == b){
        // 同属一个群体的时候不应重复叠加
        return ctr[a];
    }
    if(a > b){
        int c;
        c = a;
        a = b;
        b = c;
    }
    arr[b] = a;
    ctr[a] += ctr[b];
    return ctr[a];
}
map<string, int> namebook;
map<string, int>::iterator itra;
map<string, int>::iterator itrb;

int main(){
    std::ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for(int t = 0; t < T; t++){
        for(int i = 0; i < 200001; i++){
            arr[i] = i;
            ctr[i] = 1;
        }
        int totalnum = 0;
        int n;
        cin >> n;
        string aname, bname;
        while(n--){
            cin >> aname >> bname;
            if(namebook.find(aname)==namebook.end()){
                namebook.insert(pair<string, int>(aname, totalnum));
                totalnum++;
            }
            if(namebook.find(bname)==namebook.end()){
                namebook.insert(pair<string, int>(bname, totalnum));
                totalnum++;
            }
            itra = namebook.find(aname);
            itrb = namebook.find(bname);
            int res = ijoin(itra->second, itrb->second);
            cout << res << endl;
        }
    }
    return 0;
}
炸裂

//动态连通性问题

include

include

define MAXN 100001

using namespace std;

map name;
int sz[MAXN]; //结点的高度
int id[MAXN]; //结点的根

void init()
{
name.clear();
for(int i=1; i<MAXN; i++){
sz[i]=1;
id[i]=i;
}
}

int find(int p)
{
while(p!=id[p]) p = id[p];
return p;
}

void quick_union(int p, int q)
{
int pRoot = find(p);
int qRoot = find(q);
//cout<<pRoot<<endl;
//cout<<qRoot<<endl;
if(pRoot!=qRoot){ //根不相同
id[pRoot] = qRoot; //连接到q上
sz[qRoot] += sz[pRoot]; //高度相加
}
else{
//sz[qRoot]++;
}
cout<<sz[qRoot]<<endl;
}

int main()
{
int T,F;
string a,b;
cin>>T;
while(T–){
cin>>F;
init();
int tmp = 1; //结点的特征值
while(F–){
cin>>a>>b;
if(!name[a]){
name[a] = tmp++;
}
if(!name[b]){
name[b] = tmp++;
}
quick_union(name[a],name[b]);
}
}
return 0;
}

你当前正在回复 博客/题目
存在问题!