백준 1717 집합의 표현

 

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수또는 0이며 같을 수도 있다.

 

unionfind 집합을 merge해서 루트 노드를 보고 같은 집합인지 비교하는 알고리즘

 

 

 

 

#include <iostream>

using namespace std;
    int N,M,a,b;


int findparent(int node, int *parent)
{
if(node==parent[node])
 return node;
 
 
 else{
  parent[node] =findparent(parent[node],parent);    //재귀만 사용해서 정말 찾는 용도로만 쓸 수 있지만 parent를 업데이트 시키지 않으면 시간복잡도가 증가. 매번 집합의 길이 만큼 탐색해야 하므로 2단계 트리로 구성하기 위해 업뎃함. 
  return parent[node];
 
 }



}

void merge(int node1, int node2, int *parent, int *size)
{
   int nodex= findparent(node1,parent);
   int nodey= findparent(node2,parent);
   
   if(nodex != nodey)
   {
     if(size[nodex]<size[nodey]){
     
      parent[nodex]= nodey;
      size[nodey]+=size[nodex];
      size[nodex]=0;
     
}
       if(size[nodey]<=size[nodex]){
     
      parent[nodey]= nodex;
      size[nodex]+=size[nodey];
      size[nodey]=0;
     
}
   
   
   }
  


}

int main(void)
{
ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);  //cin과 cout이 시간이 더 걸린다는거 처음암. 편법으로 처리가능 근데도 시간 초과가 발생한다. 왜지?????????




cin >> N >>M;

int parent[N+1];
int size[N+1];

for(int i=0; i<=N; i++)
{
parent[i]=i;
size[i]=1;

}


for(int i=0; i<M; i++)
{
int x;
cin >> x >> a >> b;

if( x == 0)
{
   
merge(a,b,parent,size);

}
else if( x == 1)
{    int node1=findparent(a,parent);  //루트를 비교해서 같은 집합인지 판단. 
     int node2=findparent(b,parent);
 
if( node1 == node2)
{
cout<<"YES"<<endl;

}
else{
cout<<"NO"<<endl;
}

}

}


}