글 읽기 - 반례가 있을까요

astarter 4년 전 0

시작 도시에서 SCC를 구하고

도착지점까지 도달가능한지 여부에 따라서 도시 개수를 세주었는데요.

정답 소스코드를 빌려 몇가지 예제를 테스트 해보고

여러 예제를 만들어보았음에도 불구하고

어떤게 잘못되었는지 모르겠습니다.

제가 돌려본 예제들에서는 정답 소스코드와 인풋 아웃풋이 같이 나오는데요.

요청드립니다.

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <map>
using namespace std;

int noscc, v, e, cnt, dest;

vector<int> dfsn, set;
vector<vector<int>> E;
vector<bool> finish, visit, check;
stack<int> S;
int dfs(int i);
bool go(int i);

int main() {
	int ans, s;
	vector<int> nocity;
	noscc = cnt = ans = 0;
	
	cin >> v >> e >> s >> dest;

	E = vector<vector<int>>(v + 1, vector<int>());

	for (int i = 1, u, v; i <= e; i++) {
		cin >> u >> v;
		E[u].push_back(v);
	}
	dfsn.resize(v + 1);
	set.resize(v + 1);
	finish.resize(v + 1);

	dfs(s);
	nocity.resize(noscc + 1);

	for (int i = 1; i <= v; i++) {
		nocity[set[i]]++;
	}

	if (dfsn[dest] == 0) {
		cout << 0; 
		return 0;
	}
	check.resize(noscc + 1);
	for (int i = 1; i <= v; i++) {
		if (dfsn[i] != 0 && check[set[i]] == false) {
			visit.clear();
			visit.resize(v + 1);
			if (go(i)) {
				ans += nocity[set[i]];
			}
			check[set[i]] = true;
		}
	}
	cout << ans;
}

int dfs(int i) {
	int rst;
	S.push(i);

	dfsn[i] = ++cnt;
	rst = dfsn[i];

	for (int j : E[i]) {
		if (dfsn[j] == 0) {
			rst = min(rst, dfs(j));
		}
		else if (finish[j] == false) {
			rst = min(rst, dfsn[j]);
		}
	}

	if (rst == dfsn[i]) {
		int t;
		noscc++;
		while (true) {
			t = S.top();
			S.pop();
			finish[t] = true;
			set[t] = noscc;
			if (t == i) break;
		}
	}
	return rst;
}

bool go(int i) {
	bool reach = false;
	if (i == dest) {
		return true;
	}
	visit[i] = true;
	for (int j : E[i]) {
		if (visit[j] == false) {
			if (go(j)) {
				reach = true;
			}
		}
	}
	return reach;
}

3587jjh 4년 전 1

4 4 1 4

1 2

2 4

1 3

3 4

시작도시에서 도착도시로 가는 방법은

1->2->4 와 1->3->4가 있는데,

따라서 방문할수 있는 최대 도시수 = 3인데

위의 코드는 4를 출력합니다

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

문제

문제

출처

ICPC

반례가 있을까요

astarter 4년 전 0

3587jjh 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말