DisJoint_Set

//不相交集的概念（并查集） Union Find 
//disjoint set &&  set
//查找某個元素在那個集合 
//map <A B >  key - value
#include<iostream>
#include<set>
#include<map>
using namespace std;
typedef struct Disjoint_Set{
	int *data;
	int *parent;//負數利用起來 
	int capacity;
	int size;
	map<int,int>m;//
	//構造函數 
	Disjoint_Set(int max=10){
		capacity=max;
		size=0;
		//從1開始放元素 
		parent=new int[max+1];
		data=new int[max+1];
	}
	//析構函數
	~ Disjoint_Set(){
		delete[]parent;
		delete[] data;
	}
	bool insert(int x){
		if(size==capacity) return false;
		size++;
		data[size]=x;
		m[x]=size;//看成 
		parent[size]=-1;//改成表示大小為1 
		
		
		return true;
	}
	void print(){
		for(int i=1;i<=size;i++){
			cout<<i<<"\t";		
		}
		cout<<endl;
		for(int i=1;i<=size;i++){
			cout<<parent[i]<<"\t";		
		}
		cout<<endl;
		for(int i=1;i<=size;i++){
			cout<<data[i]<<"\t";		
		}
		cout<<endl;
	}
	//找x的樹根的下标是多少 
	int find(int x){
		typename map<int,int>::iterator it;
		it=m.find(x);
		if(it==m.end()) return -1;
		//否則找到的話，it指向的是找到的那個鍵值對，不隻是data 
		int i,rt;
		i=rt=it->second;
		while(parent[rt]>0)
			rt=parent[rt];
		
//路徑壓縮 
		int tmp;//臨時變量	
		for(;i!=rt;i=tmp){
			tmp=parent[i];
			parent[i]=rt;
		}	
			
			
	
		return rt;
	} 
	//并兩個數,不止是樹根 
	void unionset(int x,int y){
		int rx,ry;
		rx=find(x);//樹根的size 
		ry=find(y);
		
		if(rx==-1||ry==-1) return ;
		if(rx==ry) return ;
		if(parent[rx]<parent[ry]){
			parent[rx]+=parent[ry];
			parent[ry]=rx;
		}
		else{
			parent[ry]+=parent[rx];
			parent[rx]=ry;
		}	
	}
	
	
}Disjoint_Set;

int main(){
	Disjoint_Set s; 
	s.insert(11);
	s.insert(22);
	s.insert(66);
	s.insert(-5);
	s.insert(123);
	
	s.unionset(11,66);
	s.unionset(22,11);
//	s.unionset(66,-5);    
	s.print() ;

//	資料->下标->父親  傳回下标 
	 
	
	
	
	
	return 0; 
} 
           

下面兩道題，開始是用上面自己寫的代碼套進去，發現不對

再看了一下題目發現 它沒有插入操作，直接用數組把 size 和 data[size] 合到一起了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e7+10;
int vis[maxn];
void init(){
	for(int i=1;i<=maxn;i++){
		vis[i]=i;
	}
}
int find(int x)
{
	if(vis[x]==x){
		return x;
	}
	else{
		vis[x]=find(vis[x]);
		return vis[x];
	}
}
void merge(int a,int b)
{
	int p=find(a);
	int q=find(b);
	if(p==q){
		return ;
	}
	else{
		if(q>p) 
			vis[q]=p;
		else
			vis[p]=q;
		return ;
	}
	return;
}
int main()
{
	int n;
	cin>>n;
	init();
	while(n--){
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		if(a==1){
			merge(b,c);
		}
		else if(a==2){
			if(find(b)==find(c)){
				printf("YES\n");
			}
			else{
				printf("NO\n");
			}
		}
	}
	return 0;
}
           

注意題目在中說的是，從1開始連續，是以在判斷sum的時候，比較最大值是sum就🆗了，注意循環指派不要錯了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e4+10;
int vis[maxn];
int fri_ans=0,sum=0,quan_ans=0;
void init(){
	for(int i=1;i<=maxn;i++){
		vis[i]=i;
	}
}
int find(int x)
{
	if(vis[x]==x){
		return x;
	}
	else{
		vis[x]=find(vis[x]);
		return vis[x];
	}
}
void merge(int a,int b)
{
	int p=find(a);
	int q=find(b);
	if(p==q){
		return ;
	}
	else{
		if(q>p) 
			vis[q]=p;
		else
			vis[p]=q;
		
		fri_ans++; 
		return ;
	}
}
int main()
{
	int n;
	cin>>n;
	init();
	while(n--){
		int i,a,b,c;
		cin>>a>>b;
		if(b>sum) sum=b;//因為不止一次，是以要判斷看看要不要指派
		for(i=0;i<a-1;i++){
			cin>>c;
			if(c>sum) sum=c;//
			merge(b,c);
		}
	}
	
	//對于基友圈的了解，總人數-好朋友的次數 
	quan_ans=sum-fri_ans;
	cout<<quan_ans<<" "<<sum<<endl;
	int k;cin>>k;
	while(k--){
		int a,b;
		cin>>a>>b;
		if(find(a)==find(b)) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}