HDU 및 검색 집합 - 3172 가상 친구

1760 단어 알고리즘HDU
그리고 집 제 를 찾 아 보면 두 가지 서로 다른 유형의 집합 을 합 쳐 두 그루 의 나 무 를 합 친 것 과 유사 하 다 는 뜻 이다.이 점 에 속 하 는 집합 근 노드 를 찾 는 거 야.기본적으로 집 문 제 를 조사 하 는 것 은 모두 대체적인 구조 위 에 뭔 가 를 더 하면 된다.코드 템 플 릿 을 찾 아서 링크 를 열 려 면 누 르 십시오.
이 문 제 는 입력 한 두 사람 으로 구 성 된 소 셜 네트워크 서비스 (SNS) 인원 을 찾기 위해 두 사람과 앞 사람 으로 구 성 된 집합 에 얼마나 많은 요소 가 있 는 지 를 집계 하 는 것 이다.우 리 는 보조 배열 sum 을 추가 합 니 다. 두 집합 이 합 쳐 질 때 우 리 는 부모 노드 가 아래 표 시 된 sum 값 에 하위 노드 의 sum 값 을 추가 하여 이 집합 에 얼마나 많은 요소 가 있 는 지 표현 합 니 다.
#include<stdio.h>
#include<iostream>
#include<string>
#include<map>
using namespace std;
#define MAX 100000

int total;
map<string,int>A;
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
",sum[ans]);
            }        
	}
	}
}
7869 : Circular Area
[React] react router V6

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage