[백준][C++] 1976 여행 가자

www.acmicpc.net/problem/1976

1976번: 여행 가자

 

 

 

알고리즘 종류

자료구조

분리집합

 

 

사고 과정

 

 

 

구현(C++)

#include <iostream>
#include <vector>
 
using namespace std;
 
int n, m;
 
int parents[201];
int mat[201][201];
vector<int> v;
 
int get_parent(int a){
    if(parents[a] == a) return a;
    return parents[a] = get_parent(parents[a]);
}
 
void union_parents(int a, int b){
    a = get_parent(a);
    b = get_parent(b);
    
    if(a > b) parents[a] = b;
    else parents[b] = a;
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin >> n >> m;
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> mat[i][j];
        }
    }
    
    int x;
    for(int i=0; i<m; i++){
        cin >> x;
        v.push_back(x);
    }
    
    for(int i=1; i<=n; i++) parents[i] = i;
    
    for(int i=1; i<=n; i++){
        for(int j=i+1; j<=n; j++){
            if(mat[i][j] == 0) continue;
            
            if(get_parent(i) != get_parent(j)){
                union_parents(i, j);
            }
        }
    }
    
    bool flag = true;
    if(v.size()){
        for(int i=1; i<v.size(); i++){
            if(get_parent(v[0]) != get_parent(v[i])){
                flag = false;
                break;
            }
        }
    }
    
    
    if(flag) cout << "YES" << endl;
    else  cout << "NO" << endl;
}