8093 : Credibility of Witnesses
풀이
믿는다의 정의는 재귀적인데,
1. A는 A를 믿는다, 입력으로 주어진 쌍에 있는 사람들도 믿는다.
2. A가 B를 믿는다면, A는 B가 믿는 모든 사람들을 믿는다.
믿지 않는다의 정의도 재귀적인데,
1. A는 입력으로 주어진 쌍에 있는 사람들을 믿지 않는다.
2. A가 B를 믿는다면, A는 B가 믿지 않는 모든 사람들을 믿지 않는다.
그래서 모든 A에 대해서, A가 믿으면서 믿지 않는 B가 존재하는지 찾는 문제입니다.
- said koosaga
dfs를 n번 돌려서 O(n^2) 정도에 풀 수 있다.
단순 구현?
코드
#include <cstdio>
#include <vector>
using namespace std;
int n, m, res[3003], chk[3003];
vector<int> gph[3003];
void go(int now, int root) {
chk[now] |= 2;
for (int nxt : gph[now]) {
if (nxt < 0) {
chk[-nxt] |= 1;
continue;
}
if (chk[nxt] < 2) go(nxt, root);
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
gph[u].push_back(v);
}
for (int i = 1; i <= n; i++) {
go(i, i);
for (int j = 1; j <= n; j++) {
if (chk[j] == 3) res[i] = 1;
chk[j] = 0;
}
}
int r = 0;
for (int i = 1; i <= n; i++) {
if (res[i]) printf("%d\n", i), r++;
}
if (!r) puts("NIKT");
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이