并查集+STLmap
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; } } }
百度到的让cin加速的 ios::sync_with_stdio(false)一用就wrong answer? 可以用，不过不能C和C++风格输入输出混用了。
没用height也ac了？？ 一脸懵逼
一个”just”引发的血案.gif
百度到的让cin加速的 ios::sync_with_stdio(false)一用就wrong answer? 看来还是要scanf，这道题cin也来得及
#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; }
//动态连通性问题
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; }
并查集+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;
}
}
}
百度到的让cin加速的 ios::sync_with_stdio(false)一用就wrong answer?
可以用，不过不能C和C++风格输入输出混用了。
没用height也ac了？？
一脸懵逼
一个”just”引发的血案.gif
百度到的让cin加速的 ios::sync_with_stdio(false)一用就wrong answer?
看来还是要scanf，这道题cin也来得及
//动态连通性问题
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;
}