程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 並查集 - 3172 Virtual Friends

HDU 並查集 - 3172 Virtual Friends

編輯：C++入門知識

HDU 並查集 - 3172 Virtual Friends

並查集題目，並的意思就是將兩個不同類別的集合合並到一起，類似於兩棵樹合並；查的意思就是找到這個點所屬集合的根節點。基本上並查集題目都是在大體架構上面加一些東西即可。並查集代碼模板在這裡點擊打開鏈接。

這一題為了找到輸入的兩個人組成的社交網絡人數，也就是統計這兩個人與前面的人組成的集合中有多少元素。我們加一個輔助數組sum，當兩個集合並時，我們將父節點對應下標的sum值加上子節點的sum值，表達這個集合有多少元素。

#include
#include
#include
#include
using namespace std;
#define MAX 100000

int total;
mapA;
int  pa[MAX],sum[MAX];

int find_set(int x){
	if(x==pa[x])  return x;    
    pa[x]=find_set(pa[x]);  
    return pa[x];    
}

void union_set(int x,int y){
	x = find_set(x);
	y = find_set(y);
	if(x!=y){
		pa[x]=y;
		sum[y]+=sum[x];
	}
}

int main(){
	int n,m;
	string  a,b;
	while(scanf("%d",&n)!=EOF){
	while(n--){
			total=0;
            A.clear();          
            scanf("%d",&m);
            while(m--)
            {
                cin>>a>>b;
                if(A.find(a)==A.end())  
                {  
                    total++;  
                    A[a]=total;  
                    pa[total]=total;  
                    sum[total]=1;  
                    
                }  
                if(A.find(b)==A.end())  
                {  
                    total++;  
                    A[b]=total;  
                    pa[total]=total;  
                    sum[total]=1;  
                }  
                union_set(A[a],A[b]);
                int ans=find_set(A[a]);
                printf("%d\n",sum[ans]);
            }        
	}
	}
}