[BOJ/Gold 4] 백준 5594 最悪の記者(C++)

문제 링크

https://www.acmicpc.net/problem/5594

 

문제

あなたは JOI 新聞社の記者であり，スポーツ記事を担当している．

昨日までに，クロアチアでは，n 個のサッカーチームによる総当りのリーグ戦が 行われた．大会実行委員会は，試合結果と規定に基づき各チームに 1 位から n 位ま での順位をつけたようである．あなたには，一部の試合の勝敗とともに，次の情報 が伝えられた．

• 情報 1 引き分けの試合はなかった．
• 情報 2 全てのチームに異なる順位がついた．
• 情報 3 全ての 1 ≤ a < b ≤ n に対し，a 位のチームと b 位のチームの試合において， 必ず a 位のチームが勝利した．

 

あなたは記事を作成するために，一部の試合の勝敗と，伝えられた情報 1～3 をも とに，順位表を推測することにした．

入力として一部の試合の勝敗が与えられたとき，伝えられた情報に適合する順位 表を 1 つ出力するプログラムを作れ．また，出力した順位表以外に，伝えられた情 報に適合する順位表が存在するかどうかも判定せよ．

ここで，順位表とは 1 位から n 位の順にチームを並べたもののことをいう．

 

입력

1 行目には，サッカーチームの個数 n が書かれている．各チームには，1 から n ま での番号が付けられている．

2 行目には，与えられた試合の勝敗の個数 m が書かれている．

3 行目から m + 2 行目は試合の勝敗を表す．各行は空白で区切られた 2 つの整数 i, j を含み，番号 i のチームが番号 j のチームに勝利したことを表す．

n, m は 1 ≤ n ≤ 5000, 1 ≤ m ≤ 100000 をみたす．

 

출력

出力ファイルは n + 1 行からなる．

1 行目から n 行目までの n 行には，伝えられた情報に適合する順位表を出力せよ． i 行目 (1 ≤ i ≤ n) に i 位のチームの番号を出力せよ．

n + 1 行目には，出力した順位表以外に，伝えられた情報に適合する順位表が存在 するかどうかを表す整数を出力せよ．もし存在しなければ 0 を，存在する場合は 1 を出力せよ．

 

예제 입력 1

4
5
1 2
3 1
3 2
3 4
4 1

예제 출력 1

3
4
1
2
0

예제 입력 2

3
2
2 1
2 3

예제 출력 2

2
1
3
1

 

알고리즘 분류

• 위상 정렬

 

풀이

배열을 사용해서 모든 팀마다 해당 팀에게 패배한 팀을 기록해두며, 패배한 팀의 차수를 1 증가시킨다.

다음으로 위상 정렬을 사용한다.

차수가 0인 팀들만 큐에 추가하고, 큐에 존재하는 팀을 하나씩 pop하면서 팀 번호를 출력하고, 해당 팀에 패배한 팀의 차수를 1 감소시킨다.

팀의 차수가 0이 되면 큐에 추가한다. 근데 차수가 0이 되는 패배한 팀이 여러 개인 경우가 있다면 순위 테이블이 여러 개가 존재할 수 있다는 뜻이므로 마지막에 출력하는 숫자는 1이 되고, 그런 경우가 없다면 0을 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 5001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, A, B;
vector<int> Childs[MAX];
int Degrees[MAX];
int Answer;

void input() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> A >> B;
		Childs[A].push_back(B);
		Degrees[B]++;
	}
}

void settings() {
	queue<int> Q;
	for (int i = 1; i <= N; i++) {
		if (Degrees[i] == 0) {
			Q.push(i);
		}
	}

	while (!Q.empty()) {
		int Now = Q.front();
		cout << Now << "\n";
		Q.pop();

		int Count = 0;
		for (int i = 0; i < (int)Childs[Now].size(); i++) {
			int Next = Childs[Now][i];
			Degrees[Next]--;
			if (Degrees[Next] == 0) {
				Q.push(Next);
				Count++;
			}
		}

		if (Count > 1) {
			Answer = 1;
		}
	};
}

void printAnswer() {
	cout << Answer << "\n";
}

int main() {
    FASTIO

	input();
	settings();
	printAnswer();

    return 0;
}