[BOJ] 1976. 여행 가자

* 서로소 집합(union find)를 이용한다. 

* 연결되어 있는 도시들은 양방향으로 연결되고, 여행 경로는 중복이 가능하기 때문에(=최단경로가 아님)

m개의 도시들이 같은 집합에 속해있는지만 확인하면 된다. 

 

 

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87

#include <iostream> #include <vector> #include <algorithm>   #include <queue> #define MAXX 3001 using namespace std; // BOJ 여행가자 https://www.acmicpc.net/problem/1976   int n, m;   int parent[MAXX];   int find(int a) {     if (parent[a] == -1)         return a;     return find(parent[a]); } void unionFind(int a, int b) {     int pa = find(a);     int pb = find(b);       if (pa == pb)         return;       parent[pa] = pb; } bool isSameSet(int a, int b) {     int pa = find(a);     int pb = find(b);       if (pa == pb)         return true;     return false; } int main() {       ios_base::sync_with_stdio(0);     cin.tie(0);       cin >> n >> m;       for (int i = 1; i <= n; i++)     {         parent[i] = -1;     }     for (int i = 1; i <= n; i++)     {         for (int j = 1; j <= n; j++)         {             int tmp;             cin >> tmp;             if (tmp)                 unionFind(i, j);         }     }       int plan[1001] = {0};     for (int i = 0; i < m; i++)     {         cin >> plan[i];     }       bool flag = true;     int start = plan[0];     for (int i = 1; i < m; i++)     {         if (isSameSet(start, plan[i]))         {             start = plan[i];         }         else         {             flag = false;             break;         }     }     if (flag)         cout << "YES" << '\n';     else         cout << "NO" << '\n';     return 0; }