글 읽기 - 예외 케이스를 못 찾겠습니다.

memoming 6년 전 0

inDegree 가 0일때 queue에 넣고 꺼내는

위상정렬을 이용했습니다.

예외 케이스가 어떤게 있을까요 ?

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

class vertex {
public:
	vertex() { inDegree = 0; }
	vector<int> preVertexArr;
	int inDegree;
};

void pushQueue(int N, vertex* vertexArr, queue<int>* Q) {
	for (int i = 1; i <= N; i++) {
		if (vertexArr[i].inDegree == 0) {
			Q->push(i);
			break;
		}
	}
}

int main() {

	// 변수 선언부
	int N, M;					// N:가수의수 , M:PD의수
	vertex* vertexArr;
	queue<int> Q;

	// 변수 초기화부
	cin >> N >> M;
	vertexArr = new vertex[N + 1];

	for (int i = 0; i < M; i++) {
		int temp, preVertexNumber, currentVertexNumber;
		cin >> temp;
		for (int j = 0; j < temp; j++) {
			if (j == 0)
				cin >> preVertexNumber;
			else {
				cin >> currentVertexNumber;
				vertexArr[currentVertexNumber].preVertexArr.push_back(preVertexNumber);
				vertexArr[currentVertexNumber].inDegree++;
				preVertexNumber = currentVertexNumber;
			}
		}
	}

	// Algorithm

	// 초기조건 : 처음 inDegree가 0인 vertex를 찾아서 queue에 넣어둠
	pushQueue(N, vertexArr, &Q);

	if (Q.size() == 0)                                 // 순서를 정할 수 없으면 0 출력
		cout << 0 << endl;
	else {
		while (Q.size()) {
			int currentVertex = Q.front();           // queue에서 하나를 꺼내고
			vertexArr[currentVertex].inDegree = -1;  // 방문 여부 표시
			Q.pop();                                 // queue 에서 삭제

			for (int i = 1; i <= N; i++) {           // 모든 vertex를 돌면서
				for (auto j : vertexArr[i].preVertexArr) {
					if (j == currentVertex)          // 해당 vertex의 pre배열 안에 현재 vertex가 있으면
						vertexArr[i].inDegree--;     // inDegree를 하나 줄임
				}
			}

			pushQueue(N, vertexArr, &Q);             // 다시 inDegree가 0인 vertex를 찾아서 queue에 넣음.
			cout << currentVertex << endl;           // 해당 vertex를 출력
		}
	}

	return 0;
}

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

문제

문제

출처

ICPC

예외 케이스를 못 찾겠습니다.

memoming 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말