백준 - 1976 여행 가자

시나모온 2020. 7. 3. 05:11

문제 링크입니다 : https://www.acmicpc.net/problem/1976

1976번: 여행 가자

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인

www.acmicpc.net

#include <cstdio>

using namespace std;

int parent[201];
int N, M;

int findParent(int a) {
    if(parent[a] == a) return a;
    return parent[a] = findParent(parent[a]);
}

void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);

    if(a > b) parent[a] = b;
    else parent[b] = a;
}


int main() {
    scanf("%d %d", &N, &M);

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

    int conn;
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            scanf("%d", &conn);
            if(conn) {
                unionParent(i, j);
            }
        }
    }
    
    int arr[1001];
    for(int i = 0; i < M; i++) {
        scanf("%d", &arr[i]);
    }

    for(int i = 1; i < M; i++) {
        if(findParent(arr[i - 1]) != findParent(arr[i])) {
            printf("NO");
            return 0;
        }
    }

    printf("YES");


    return 0;
}

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

저작자표시 (새창열림)