https://www.acmicpc.net/problem/28102
태그 : 그래프, 유니온파인드, 이분 그래프
사고 과정
처음 읽고나서 드는 생각은 k 조건이 너무 말도 안되게 크다는 것이였다.
여기서 오히려 거리를 실제로 구하는건 이상한 짓이니, 다른 방법을 찾아야 한다는 것을 떠올릴 수 있다.
페어와 이 문제를 읽어보았는데, 페어가 홀짝성에 대한 이야기를 꺼냈다.
이 사람과 얘기하다보면 느끼는건데, 직관이나 관찰이 정말 좋다고 생각한다.
암튼 머리를 싸매다가 태그를 열고.. 이분그래프를 보게 되었다.
그래서 이 기회에 이분 그래프를 공부하게 되었다.
이분 그래프
https://www.acmicpc.net/problem/1707
기억에서 지우고 있었는데 이분 그래프 문제를 푼 적도 있었다. 하지만 기억에 남는 게 없어서, 다시 공부하게 되었다.
구글링하면 이런 이미지를 쉽게 찾아볼 수 있다. 적의 적은 내친구 라는 느낌의 그래프이다.
이분 그래프가 뭐냐 하는것은 제쳐두고, 이분 그래프와 관련된 몇 가지 특징을 살펴보면..
어떤 그래프가 이분 그래프라면 홀수 길이의 싸이클이 생기지 않는다.
직관적으로, 홀수 싸이클일 경우 위와 같은 상황이 나오게 됨을 떠올릴 수 있다.
다시 말하면, 어떤 그래프가 이분그래프가 아니라면 반드시 홀수 길이의 싸이클이 존재한다.
이분 그래프라면 노드 간 거리의 홀짝 여부는 같은 그룹에 속하느냐에 따라 정해진다.위의 그림에서 조금 더 생각해보면, 건너 건너는 모두 같은 그룹에 속하므로 짝수 거리,
그렇지 않으면 홀수 거리임을 생각해볼 수 있다.
이러한 특징들을 바탕으로 이 문제를 관찰하면,
사실 k의 크기나 실제 노드 사이의 최단경로는 이 문제의 핵심이 아님을 알 수 있다.
풀이
k가 홀수라고 하자. 이 때는 두 그래프가 연결만 되어있다면 k의 배수 경로가 가능하다.
결국 k의 배수들이 홀-짝이 반복해서 나타나므로, 연결만 되어있다면 k의 배수가 될 때 까지
도착노드와 그 옆 노드를 왔다갔다 하다보면 된다.
k가 짝수라면? 배수가 짝수만 등장한다. 이 때, 이분그래프의 성질을 활용해보면,
1. 두 노드가 속한 그래프가 이분그래프라면? 같은 그룹인지 판별해본다.
2. 이분그래프가 아니라면, 홀수 싸이클이 존재한다. 홀수 싸이클을 타다 보면 짝/홀로 간선 길이를 조정할 수 있으므로,
반드시 k의 배수를 만들 수 있다.이 논리를 적용하면 정답을 받을 수 있다.
코드
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 1e18
typedef long long ll;
int n, m, q;
vector<int> v[100001];
int parent[100001];
int color[100001];
int bPartial[100001];
string ans;
/*
1) k가 홀수 -> 배수가 홀, 짝, 홀, 짝 -> 간선이 짝이든 홀이든 연결만 된다면 결국 홀,짝 암거나 서로 곱하면 되니까.
2) k가 짝수 -> 짝수만 나옴 -> 거리가 짝수면 OK 거리가 홀수면? 홀수 싸이클이 필요
홀수 사이클이 있으면 반드시 홀-짝을 만들 수 있다. 이분 그래프에는 홀수 싸이클이 생기지 않는다.
->두 점이 속한 그래프가 동일하고, 이분그래프가 아닌 경우 -> 그냥 무조건 가능
이분그래프인 경우 -> 같은 그룹이면 가능, 아니면 안됨
*/
int find(int node) {
if (parent[node] == node) {
return node;
}
return parent[node] = find(parent[node]);
}
void merge(int a, int b) {
int pa = find(a);
int pb = find(b);
if (pa != pb) {
parent[pa] = pb;
}
}
//이분그래프가 아니라면 해당 그래프 전부 -1 기록, 이분그래프라면 1/2로 구분
bool make_graph(int node) {
queue<int> q;
q.push(node);
color[node] = 1;
while (!q.empty()) {
int front = q.front();
q.pop();
if (find(node) != find(front)) {
merge(node, front);
}
int nextColor = 3 - color[front];
for (int i = 0; i < v[front].size(); ++i) {
int next = v[front][i];
if (!color[next]) {
color[next] = nextColor;
q.push(next);
}
else {
if (color[next] != nextColor) {
return false;
}
}
}
}
return true;
}
void fill_graph(int node) {
queue<int> q;
q.push(node);
color[node] = -1;
while (!q.empty()) {
int front = q.front();
q.pop();
if (find(node) != find(front)) {
merge(node, front);
}
for (int i = 0; i < v[front].size(); ++i) {
int next = v[front][i];
if (color[next] != -1) {
color[next] = -1;
q.push(next);
}
}
}
}
void solve() {
for (int i = 1; i <= n; ++i) {
if (!color[i]) {
bool flag = make_graph(i);
if (!flag) {
fill_graph(i);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> q;
int a, b, c, k;
for (int i = 1; i <= n; ++i) {
parent[i] = i;
}
while (m--) {
cin >> a >> b >> c;
v[a].push_back(b);
v[b].push_back(a);
}
solve();
while (q--) {
cin >> a >> b >> k;
//홀수
if (k % 2) {
ans = find(a) == find(b) ? "Yes" : "No";
}
else {
if (find(a) == find(b)) {
if (color[a] == -1) {
ans = "Yes";
}
else {
if (color[a] == color[b]) {
ans = "Yes";
}
else {
ans = "No";
}
}
}
else {
ans = "No";
}
}
cout << ans << '\n';
}
}