백준 1976번: 여행 가자 (C++)

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

1976번: 여행 가자

---

Solved By: Union-Find

#include <iostream>
#include <vector>
#define MAX 201
#define pii pair<int, int>
using namespace std;

vector<pii> edges;
vector<int> trip;
int parent[MAX];

int n, m;

int getRoot(int node){
    if(node == parent[node]) return node;
    else return parent[node] = getRoot(parent[node]);
}

void unionNodes(int a, int b){
    int rA = getRoot(a);
    int rB = getRoot(b);
    
    if(rA > rB){
        parent[rB] = rA;
    }
    else{
        parent[rA] = rB;
    }
}

bool find(int a, int b){
    int rA = getRoot(a);
    int rB = getRoot(b);
    
    if(rA != rB) return 1;
    else return 0;
}

int main(){
    cin >> n >> m;
    bool a;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> a;
            if(a == 1){
                edges.push_back({i, j});
            }
        }
    }
    
    for(int i = 1; i <= n; i++) parent[i] = i;
    for(int i = 0; i < edges.size(); i++){
        unionNodes(edges[i].first, edges[i].second);
    }
    
    for(int i = 0; i < m; i++){
        int q; cin >> q;
        trip.push_back(q);
    }
   
    bool check = 1;
    
    for(int i = 1; i < trip.size(); i++){
        if(find(trip[i - 1], trip[i])) check = 0;
    }
    
    if(check == 0) cout << "NO";
    else cout << "YES";
    
    return 0;
}