- 주어진 그래프가 사이클이 없으므로, 나머지를 어떻게 연결하던 사이클이 없는 그래프는 반드시 생성 가능함
- 나머지 간선을 한 방향으로 연결해보고, 사이클이 생기면 반대방향이 정답
- 사이클 판단에 N+K+M, M번 반복하므로 시간안에 해결
/*
Prob
2021 SCPC 1차 예선 3번 No Cycle
*/
#include <bits/stdc++.h>
#include <fstream>
#define N 510
using namespace std;
int tc, n, k, m;
vector<int> edges[N];
bool checked[N], finished[N];
bool hasCycle(int now) {
if (checked[now]) return !finished[now];
checked[now] = true;
for (int next : edges[now])
if (hasCycle(next)) return true;
finished[now] = true;
return false;
}
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(0);
cin >> tc;
for (int tt = 1; tt <= tc; tt++) {
for (int i = 1; i <= n; i++) edges[i].clear();
cin >> n >> m >> k;
int a, b;
for (int i = 0; i < m; i++) {
cin >> a >> b;
edges[a].push_back(b);
}
cout << "Case #" << tt << "\n";
for (int i = 0; i < k; i++) {
memset(checked, 0, sizeof(checked));
memset(finished, 0, sizeof(finished));
cin >> a >> b;
edges[a].push_back(b);
if (hasCycle(a)) {
edges[a].pop_back();
edges[b].push_back(a);
cout << 1;
} else
cout << 0;
}
cout << "\n";
}
return 0;
}
'Coding Test > codeground' 카테고리의 다른 글
[SCPC 2021 1차 예선] 이진수 (0) | 2022.06.25 |
---|---|
[2021 SCPC 예선 1차] 친구들 (0) | 2022.06.24 |
[SCPC 1회 예선] 등차수열 (0) | 2022.01.05 |
회로판 위의 배터리 / SCPC 1차 예선 (0) | 2022.01.04 |
균일수 / SCPC 1차 예선 (0) | 2021.11.23 |
Comment