글 읽기 - 30%에서 틀리는데 반례가 무엇일까요?

kth990303 3년 전 3

scc 그룹들을 다 구해줬습니다.

그 후, scc끼리 위상정렬을 실시 후

현재 scc가 여행이 가능할 경우, 다음 scc도 여행이 가능하므로 최대를 갱신해주는 방식으로 값을 구했습니다.

그런데 30%에서 틀리네요. 틀린 이유나 반례를 알 수 있을까요?

제가 만들어서 넣어본 반례를 코드 아래에 첨부하겠습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cstring>
using namespace std;
const int MAX = 10001;
int N, M, S, T, num;
int id, finished[MAX], d[MAX], in[MAX], sccNum[MAX];
vector<int> v[MAX];
vector<int> SCC[MAX];
vector<int> inScc[MAX];
stack<int> s;
bool visit[MAX];
int dp[MAX];
// SCC를 구해줍니다.
int dfs(int x) {
	d[x] = ++id;
	s.push(x);

	int p = d[x];
	for (auto i : v[x]) {
		if (!d[i])
			p = min(p, dfs(i));
		else if (!finished[i])
			p = min(p, d[i]);
	}
	if (p == d[x]) {
		vector<int> scc;
		int prev = -1;
		++num;
		while (1) {
			int t = s.top();
			s.pop();
			scc.push_back(t);
			finished[t] = true;
			prev = t;
			sccNum[t] = num;
			if (t == x)
				break;
		}
		SCC[num] = scc;
	}
	return p;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> M >> S >> T;
	for (int i = 0; i < M; i++) {
		int s, e;
		cin >> s >> e;
		v[s].push_back(e);
	}
    // scc를 구해줍니다.
	for (int i = 1; i <= N; i++) {
		if (!d[i])
			dfs(i);
	}
    // scc끼리 DAG를 만들기 위해 indegree를 구해줍니다.
	for (int i = 1; i <= N; i++) {
		for (auto j : v[i]) {
			if (sccNum[i] != sccNum[j]) {
				inScc[sccNum[i]].push_back(sccNum[j]);
				in[sccNum[j]]++;
			}
		}
	}
	queue<int> q;
    // 현재 scc그룹 개수들의 여행 가능 지역 수 (dp)를 갱신해준 후,
    // indegree가 0인 그룹들을 위상정렬을 시작합니다.
	for (int i = 1; i <= num; i++) {
		dp[i] = SCC[i].size();
		if (!in[i])
			q.push(i);
	}
    // 또한, 시작점의 scc그룹은 방문이 가능합니다.
	visit[sccNum[S]] = true;
    // 이제 위상정렬을 시작합니다.
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (auto i : inScc[cur]) {
			if (visit[cur]) {
				visit[i] = true;
				dp[i] = max(dp[sccNum[i]], dp[cur] + (int)SCC[i].size());
			}
			if (--in[i] == 0)
				q.push(i);
		}
	}
    // 방문이 불가능하면 0, 가능하면 dp배열 여행이 가능한 지역 수를 출력합니다.
	if (!visit[sccNum[T]])
		cout << 0 << "\n";
	else
		cout << dp[sccNum[T]] << "\n";
}

/*
넣어본 반례
6 7 5 6
1 2
2 3
3 4
4 2
4 6
6 4
5 3
ans: 5

9 13 1 8
1 2
2 1
2 3
3 2
2 4
3 5
5 9
9 5
9 6
4 6
6 7
7 8
8 4
ans: 9

9 13 6 9
1 2
2 1
2 3
3 2
2 4
3 5
5 9
9 5
9 6
4 6
6 7
7 8
8 4
ans: 0

9 13 1 9
1 2
2 1
2 3
3 2
2 4
3 5
5 9
9 5
9 6
4 6
6 7
7 8
8 4
ans: 5

7 7 6 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1
ans: 7
*/

kth990303 3년 전 2

전 바보인가 봅니다.

dp식 잘보면 max 구하는 과정이 이상하네요.

반례데이터들이 저에게 큰 힘이 됐으므로 위 코드는 남겨두겠습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

30%에서 틀리는데 반례가 무엇일까요?

kth990303 3년 전 3

kth990303 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말