【解題報告】 ZOJ 3641 Information Sharing - 并查集+模拟

/*
	ZOJ 3641 Information Sharing 并查集+模拟
	題意：給出了一些人對應了幾個數字（information）
	然後又有一些人會分享數字（share information）分享是雙向的，取并集
	最後會問某些人在此刻擁有哪些數字（information he has gotten）
	做法：由于數字的個數才1000（at most 1000 distinct information）
	是以每個人用一個集合表示,每個人集合的大小不會很大，然後分享的操作就是
	并查集并的過程，而輸出隻需要直接輸出集合的大小即可。

*/


#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define CLR(c,v) memset(c,v,sizeof(c))
using namespace std;
const int N = 1e5 + 5;

map <string ,int>list;
set<int > dset[N];
int father[N];
int n_people = 0;

int getid(string name){
	if(list.find(name) == list.end()){
		// 在這裡初始化
		list[name] = ++n_people;
		father[n_people] = n_people;
		dset[n_people].clear();
	}
	return list[name];
}

int find(int x){
	if(x == father[x]) return x;
	return father[x] = find(father[x]);
}

void Union(int name1,int name2){
	int f1 = find(name1);
	int f2 = find(name2);
	if(f1 == f2)return;
	if(dset[f1].size() > dset[f2].size()){
		swap(f1,f2);
	}
	for(set <int >::iterator it = dset[f1].begin() ; it != dset[f1].end() ; it++){
		dset[f2].insert(*it);
	}
	father[f1] = f2;
}

int main(){
	//freopen("in.txt","r",stdin);
	int T;
	while(~scanf("%d",&T)){
		list.clear();
		n_people = 0;
		while(T--){
			string ins,name1;
			cin >> ins >> name1;
			int id1 = getid(name1);
			if(ins[0] == 'a'){
				int m;scanf("%d",&m);
				for(int i = 0; i < m ; i++){
					int a;scanf("%d",&a);
					dset[id1].insert(a);
				}
			}else if(ins[0] == 's'){
				string name2;
				cin >> name2;
				Union( id1 , getid(name2));
			}else{
				id1 = find(id1);
				cout << dset[id1].size() << endl;
			}
		}
	}
	return 0;
}

/*
這個是用了兩個map的程式，TLE了。。。
後來看了看人家寫的，發現轉成int的就可以了。。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define CLR(c,v) memset(c,v,sizeof(c))
using namespace std;
const int N = 1000 + 5;

map <string ,string>father;
map <string ,set<int > > sdmap;

void debug(){

}

string find(string& name){
	if(name == father[name]) return name;
	return father[name] = find(father[name]);
}

void Union(string& name1,string& name2){
	string f1 = find(name1);
	string f2 = find(name2);

	if(sdmap[f1].size() > sdmap[f2].size()){
		swap(f1,f2);
	}
	for(set <int >::iterator it = sdmap[f1].begin() ; it != sdmap[f1].end() ; it++){
		sdmap[f2].insert(*it);
	}
	father[f1] = f2;

}

int main(){
	//freopen("in.txt","r",stdin);
	int T;
	while(~scanf("%d",&T)){
		sdmap.clear();
		father.clear();
		while(T--){
			string ins;
			cin >> ins;
			if(ins[0] == 'a'){
				string name;int m;
				cin >> name >> m;
				father[name] = name;
				for(int i = 0; i < m ; i++){
					int a;scanf("%d",&a);
					sdmap[name].insert(a);
				}
			}else if(ins[0] == 's'){
				string name1,name2;
				cin >> name1 >> name2;
				Union(name1,name2);
			}else{
				string name;
				cin >> name;
				name = find(name);
				cout <<sdmap[name].size() << endl;
			}
		}
	}
	return 0;
}
*/