글 읽기 - 위상정렬 반례에서 answer.size()!=n 인 경우가 무엇일까요??

wown252 2년 전 0

코드에서

if(answer.size()!=n){cout<<0;} 부분이 없을 때는 틀렸습니다가 뜨는데

if(answer.size()!=n){cout<<0;} 를 추가해주자마자 맞았다고 뜨더라구요, 근데 위상정렬에서는 이 부분이 없어도 구현이 되는게 아닌가 싶어서 여쭙습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#define ioboost ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

//1207 ~ 
queue<int> order;
queue<int> answer;
set<int> front[1001];
set<int> back[1001];

int main(){
    ioboost;
    int n,m;
    cin >> n >> m;
    for(int i=0; i<m; i++){
        int num;
        cin >> num;
        if(num > 1){
            int prev, next;
            cin >> prev;
            for(int j=1; j<num; j++){
                cin >> next;
                back[prev].insert(next);
                front[next].insert(prev);
                if(front[prev].count(next)>0){
                    cout<<0;
                    return 0;
                }
                prev = next;             
            }
        }else if(num == 1){
            int throwaway;
            cin >> throwaway;
        }
    }

    for(int i=1; i<=n; i++){
        if(front[i].size()==0){
            order.push(i);
        }
    }

    while(!order.empty()){
        int curr = order.front();
        order.pop();
        answer.push(curr);
        set<int>::iterator it = back[curr].begin();
        for(; it!=back[curr].end(); it++){
            int next = *it;
            front[next].erase(curr);
            if(front[next].size()==0){
                order.push(next);
            }
        }
    }

    if(answer.size()!=n){cout<<0;} //ㅇㅣ게 왜.. 
    else{
        while(!answer.empty()){
            cout<<answer.front()<<'\n';
            answer.pop();
        }
    }
    
}

경우에 따라서 남일이가 모두를 만족하는 순서를 정하는 것이 불가능할 수도 있다. 예를 들어, 세 번째 보조 PD가 순서를 2 3 대신에 3 2로 정해오면 남일이가 전체 순서를 정하는 것이 불가능하다. 이번에 남일이는 우리 나라의 월드컵 4강 진출 기념 음악제의 PD를 맡게 되었는데, 출연 가수가 아주 많다. 이제 여러분이 해야 할 일은 보조 PD들이 가져 온 순서들을 보고 남일이가 가수 출연 순서를 정할 수 있도록 도와 주는 일이다.

문제에 반례가 있습니다

wown252 2년 전 0

아하 23 32처럼 서로 반대되는 싸이클이 생기는 것 제외하고도 다른 싸이클이 만들어질 수 있어서 그 부분을 예외처리를 제가 못했던 거였나보네요!! 답변감사드립니다.

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

문제

문제

출처

ICPC

위상정렬 반례에서 answer.size()!=n 인 경우가 무엇일까요??

wown252 2년 전 0

cchccc 2년 전 0

wown252 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말