글 읽기 - c++ 위상정렬 틀린 부분을 모르겠어요(주석 있음)

plan222 3년 전 1

그냥 18%에서 틀렸습니다로 나옵니다.

중복을 받아도 모두 degree를올리고 간선을 중복해서 추가하는 식으로 했습니다.

어떤 점이 틀렸을까요?

-------------------------------------

10이상의 수를 char에 넣으려 한 어이없는 실수를 했네요~

#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <set>

using namespace std;
int temp;
#define MIN(A,B) A<B?A:B;
#define MAX(A,B) A>B?A:B;
#define SWAP(A,B) {temp=A;A=B;B=temp;}

char str[2001]; //정답을 출력할 문자열
int numOfPrev[1001]; //indegree
vector<int> pointing[1001]; //다음 가수를 가르킴 (간선역할)
queue<int> noPrev;

int main()
{
	int n, m,num,prev,next,singer;
	cin >> n >> m;
	//입력받기
	for(int i=0;i<m;i++)
	{
		scanf("%d", &num);
		for(int k=0;k<num;k++)
		{
			scanf("%d", &singer);
			if (!k)
			{
				next = singer;
			}
			else
			{
				prev = next;
				next = singer;
				numOfPrev[next]++; //방금 받은 가수의 차수를 증가시킴
				pointing[prev].push_back(next); //그 전에 받은 가수가 next를 가르킴
			}
		}
	}
	//큐에 넣고 돌리기
	for (int i = 1; i <= n; i++)
	{
		if (!numOfPrev[i]) //차수가 0이면 큐에넣기
		{
			noPrev.push(i);
		}
	}
	int strPointer = 0,tmp,tmp2;

	while (!noPrev.empty())
	{
		tmp = noPrev.front(); //큐에서 뽑기
		noPrev.pop();

		str[2*strPointer] = tmp+'0'; //출력할 char 배열에 집어넣기
		str[2 * strPointer + 1] = '\n';
		strPointer++;

		while (!pointing[tmp].empty()) //이 가수와 연결된 가수들의 차수를 낮춤
		{
			tmp2 = pointing[tmp].back();
			pointing[tmp].pop_back();
			numOfPrev[tmp2]--;
			if (numOfPrev[tmp2]==0) //차수가 0되면 큐에 넣음
			{
				noPrev.push(tmp2);
			}
		}
	}

	if (strPointer != n) //사이클이 존재하면 0만 출력
	{
		str[0] = '0';
		str[1] = '\0';
	}
	else
	{
		str[2 * strPointer-1] = '\0';
	}

	printf("%s", str);
}

anycar8515 17일 전 0

저도 정답 문자열의 길이를 2 * N인지 검증하며 불가능 유무를 체크했네요 ㅋㅋㅋㅋㅋㅋ 감사합니다...

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

문제

문제

출처

ICPC

c++ 위상정렬 틀린 부분을 모르겠어요(주석 있음)

plan222 3년 전 1

anycar8515 17일 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말