백준 1717번:집합의 표현

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

이 문제는 같은 집합에 있는지 아닌지만 파악하면 되므로 유니온 파인드를 이용했다.

그리고 입력 값이 많이 들어갈 것을 생각해서 

cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false); 

이것들을 추가 했다.

0이면 유니온 처리 해주고 1이면 루트노드를 비교해서 같으면 YES 아니면NO가 나오게 했다.

유니온 파인드만 알고 있으면 쉬운 문제다.

#include <iostream>
using namespace std;
int parent[1000001];
int find(int x){             //유니온 파인드
  if (x==parent[x]){
    return x;
  }
  else{
    int y = find(parent[x]);
    parent[x] = y;
    return y;
  }
}
void Union(int x,int y){
  x = find(x);
  y = find(y);
  parent[y] = x;
}
int main(){
    cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
    int n ,m;
    cin >>n>>m;
    for(int i=1;i<=n;i++){
        parent[i]=i;
    }
    while(m--){                     
        int input,a ,b;
        cin >>input>>a>>b;
        if(input ==0){              //0이면 합쳐준다
            Union(a,b);
        }
        if(input==1){
            if(find(a)==find(b)){                 //루트노드가 같으면 같은 집합이므로 YES
                cout <<"YES" <<'\n';
            }
            else{                                  //아니면 NO
                cout << "NO" << '\n'; 
            }
        }
    }

}