728x90
반응형
1976번: 여행 가자
문제
https://www.acmicpc.net/problem/1976
풀이
인접 행렬을 입력받아 인접한 도시끼리 union 시켜준 다음 여행 계획에 포함되어 있는 도시들이 모두 같은 집합 안에 있는지 즉, find 값이 모두 같은지 확인하면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
vector<int> p;
int find(int x) {
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x < y)
p[y] = x;
else
p[x] = y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
p.resize(n + 1);
iota(p.begin(), p.end(), 0);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
int x;
cin >> x;
if (x == 1)
merge(i, j);
}
vector<int> v(m);
for (int i = 0; i < m; i++)
cin >> v[i];
int x = find(v[0]);
string ans = "YES";
for (int i = 1; i < m; i++)
if (x != find(v[i]))
ans = "NO";
cout << ans;
return 0;
}
728x90
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
[백준 / BOJ] C++ 1774 우주신과의 교감 (10) | 2023.03.29 |
---|---|
[백준 / BOJ] C++ 9373 복도 뚫기 (12) | 2023.03.28 |
[백준 / BOJ] C++ 1717 집합의 표현 (2) | 2023.03.28 |
[백준 / BOJ] C++ 2638 치즈 (0) | 2023.03.28 |
[백준 / BOJ] C++ 2143 두 배열의 합 (2) | 2023.03.28 |