글 읽기 - 시간을 줄이기 위해서 추가한 구문이 오작동을 일으키는데 이유를 모르겠습니다.

dladydwo123 5년 전 0

주석 처리한 부분을 포함하여 제출시 오작동을 일으킵니다. 왜 틀리는지 잘 모르겠습니다.

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

int N, M;
bool table[10001][10001] = { 0, };
int info[10001];
vector<int> v[10001];

void dfs(int start, int prev) {
	int size = v[prev].size();

	for (int i = 0; i < size; i++) {
		if (table[start][v[prev][i]] != 1) { //방문한적이 없다.
			info[start]++;
			table[start][v[prev][i]] = 1; //방문 표시.

			dfs(start, v[prev][i]);
		}
	}

}

int main() {
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		v[b].push_back(a);
	}

	for (int i = 1; i <= N; i++) { //start == i
		table[i][i] = 1;
		info[i] = 1;
		int size = v[i].size();

		for (int j = 0; j < size; j++) {
			/* 이부분을 추가하면 틀렸습니다. 가 나옵니다.
            // dfs내부가아닌, 첫 for문 속에선 v[i][j] < i이면, v[i][j]을 시작으로 하는 부분은 
            // 이미 모든 검사가 완료된 상태임으로 그대로 이용할 수 있다고 생각했습니다.
 			if (v[i][j] < i) { //이전에 구해두었던 값을 가져옴.
				for (int k = 1; k <= N; k++) {
					if (table[i][k] == 0 && table[v[i][j]][k] == 1) {
						table[i][k] = table[v[i][j]][k];
						info[i]++;
					}
				}

				continue;
			}
			*/
			if (table[i][v[i][j]] != 1) {
				info[i]++;
				table[i][v[i][j]] = 1;
				dfs(i, v[i][j]);
			}
		}
	}

	int max_num = -1;
	for (int i = 1; i <= N; i++) 
		max_num = max_num < info[i] ? info[i] : max_num;
	

	for (int i = 1; i <= N; i++) 
		if (max_num == info[i]) 
			cout << i << ' ';

	return 0;
}

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

문제

문제

출처

ICPC

시간을 줄이기 위해서 추가한 구문이 오작동을 일으키는데 이유를 모르겠습니다.

dladydwo123 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말