77. 친구인가

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

9 7

1 2

2 3

3 4

4 5

6 7

7 8

8 9

3 8

 

출력예제 1

NO

 

풀이 

- Find & Union 알고리즘

- 1차원 배열인 unf를 사용해 트리형태를 구현한다

- Find와 Union 함수가 필요

 

(1) Find 함수 : 집합번호를 리턴하고 서로의 집합이 다를 시에 서로 합친다. ex ) {1}, {2} => {1, 2}

(2) Union함수

- 인덱스 번호와 집합번호가 같으면 해당 v값을 return

- 아닐시 unf[v]에 들어있는 값으로 루트 노드를 찾아 넣어준다 => unf[v]=Find(unf[v])

 

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int unf[1001]; //1차원 배열로 트리형태 구현

//77. 친구인가(Disjoint-set : Union & find 알고리즘) 서로소 집합
int Find(int v){
    //연결된 루트노드가 리턴된다.
    if(v==unf[v]) return v;
    else return unf[v]=Find(unf[v]);
}

void Union(int a, int b){
    a=Find(a); //a의 집합번호를 리턴
    b=Find(b); //b의 집합번호를 리턴
    if(a!=b) unf[a]=b; //서로의 집합이 다르면 서로 합침
}

int main(){
    int n, m, a, b;
    scanf("%d %d", &n, &m); //반 학생수 n, 숫자쌍 m
    for(int i=1;i<=n;i++){
        unf[i]=i; //초기화
    }
    for(int i=1;i<=m;i++){
        scanf("%d %d", &a, &b);
        Union(a, b);
    }
    scanf("%d %d", &a, &b);
    a=Find(a);
    b=Find(b);
    if(a==b) printf("YES");
    else printf("NO");
    return 0;
}