글 읽기 - 반례를 못찾겠습니다...

kwon6460 5년 전 0

a[] : 자식의 수

c[] : 최종 자식의 수

자식의 수(a)가 0이면서 visit(false)인 노드를 찾는다.
해당 노드의 visit을 true로 변경한다.
자식을 부모로 하고있는 노드의 최종 자식의 수(c)를 모두 1 증가 시키고, 자식의 수(a)를 1씩 감소시킨다.
부모노드들중 자식의 수(a)가 0이고, 자식노드의 index보다 작은 부모노드들 중 가장 작은 노드부터 다시 검색한다.

문제1 : 예제는 맞다고 나오는데 출력시 틀렸다고 나옵니다.

걱정1 : 최악의 경우 O(n^2)이 나올거라 생각됩니다.

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int n, m, a[10001], c[10001], maxi, an;	//a 자식의 수, c 최종 자식의 수
vector<int> v[10001];	                //v 자식 -> 부모
bool visit[10001];

int main(){
	scanf("%d %d", &n, &m);
	while (m--){
		int x, y;
		scanf("%d %d", &x, &y);
		a[y]++;
		if (a[x] > an)
			an = a[x];
		v[x].push_back(y);
	}
	for (int i = 1; i <= n; i++)
		c[i] = 1;

    //자식이 없는 노드를 하나씩 제거해 나감
	for (int i = 1; i <= n; i++){
		int temp = i;
		if (a[i] == 0 && !visit[i]){
			visit[i] = 1;
			int size = v[i].size();
			for (int j = 0; j < size; j++){
				c[v[i][j]] += c[i];
				a[v[i][j]]--;
				if (a[v[i][j]] == 0 && i > v[i][j])
					temp = v[i][j] - 1;
			}
		}
		i = temp;
	}

	for (int i = 1; i <= n; i++)
		maxi = maxi > c[i] ? maxi : c[i];

	for (int i = 1; i <= n; i++)
		if (c[i] == maxi){
			printf("%d ", i);
		}
	printf("\n");
}

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

문제

문제

출처

ICPC

반례를 못찾겠습니다...

kwon6460 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말