글 읽기 - 위상정렬 문제 틀린 부분 못찾겠습니다..

ezelay 8년 전 0

예제는 맞고 50%정도까지 채점되는데 틀리다고 하네요

주석으로 코드 설명 달아놨습니다

어디서 틀렸는지 알려주시면 감사하겠습니다

#include <cstdio>
#include <iostream>
using namespace std;
int singerlink[1001][1001];
int cnt[1001];//들어오는 간선 수
int order[1001];//순서 한 경우 저장

int main(){
	int N, M;//N은 가수 수, M은 PD수
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; ++i){
		int num; scanf("%d", &num);
		int nxt;
		int prev = 0;
		for (int j = 0; j < num; ++j){
			scanf("%d", &nxt);
			singerlink[prev][nxt] = 1;
			if (j == 0)singerlink[prev][nxt] = 0;//처음엔 사실 연결 된게 아니므로 원래대로
			else cnt[nxt]++;//들어오는 간선 수 증가했으니까
			prev = nxt;
		}
	}

	//위상정렬 가능한 경우
	int i;
	for (i = 1; i <= N; ++i){
		//진입 간선이 없는 노드 선택 
		bool found = false;
		int nodenum;
		for (int j = 1; j <= N; ++j){
			if (cnt[j] == 0){//그중 가장 빠른 노드 선택
				cnt[j] = -1;//제거
				found = true;
				nodenum = j;
				break;
			}
		}
		if (!found)break;
		order[i] = nodenum;//노드 순서 정보 저장
		//이 노드에서 나가는 간선들 모두 제거
		for (int j = 1; j <= N; ++j){
			if (singerlink[nodenum][j]){
				//nodenum에서 출발해 연겨로딘 간선이면 제거
				singerlink[nodenum][j] = 0;
				cnt[j]--;//j로 들어오는 간선 수 하나 감소
			}
		}
	}

	if (i == N + 1){//길이 N인 것 찾은 경우
		for (int i = 1; i <= N; ++i)printf("%d\n", order[i]);
	}
	else {//찾기 실패 
		cout << 0 << endl;
	}

	return 0;
}

pps789 8년 전 1

간선을 제거할 때, singerlink가 2 이상일 수 도 있습니다.

ezelay 8년 전 2

중복 간선이 들어 오는 경우가 있었네요 해결했습니다 감사합니다

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

문제

문제

출처

ICPC

위상정렬 문제 틀린 부분 못찾겠습니다..

ezelay 8년 전 0

pps789 8년 전 1

ezelay 8년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말