(1976) 여행 가자

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

단계별로 풀어보기

34단계(유니온 파인드 1) 2번째

 

 

 

유니온 파인드를 이용해 그래프에서 정점의 연결 여부를 확인할 수 있다. 그래프에서 간선으로 이어진 모든 두 정점을 유니온 파인드에서 병합하면 이어진 정점끼리는 같은 집합에 속해있게 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;
  
  vector<int> uf(n+1), v(m);
  
  for(int i=1;i<=n;i++)  uf[i]= i;
  
  auto find= [&](auto self, int x) -> int {
    if(uf[x]==x)  return x;
    else  return uf[x]= self(self, uf[x]);
  };
  
  auto merge= [&](int x, int y){
    x= find(find, x);
    y= find(find, y);
    
    uf[y]= x;
  };
  
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      int t;
      
      cin >> t;
      
      if(t)  merge(i, j);
    }
  }
  
  for(int i=0;i<m;i++)  cin >> v[i];
  
  for(int i=1;i<m;i++){
    if(find(find, v[i-1])!=find(find, v[i])){
      cout << "NO";
      
      return 0;
    }
  }
  
  cout << "YES";
  
  return 0;
}