글 읽기 - 케이스 질문 드립니다.

leechhe 8년 전 0

DFS로 탐색 후 return 할 때 dag 배열에 push 하고

순서를 뒤집어서 답을 찾습니다.

순서가 불가능한 경우는 finished 배열로 체크를 하였습니다. 나름 만들어서 돌려봤는데... 부탁드려요 ㅠㅠ

#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>    //priority queue
#include <functional>
#include <cmath>
#include <stack>
#include <iostream>
#include <cstdlib>
#include <limits>
#include <cstring>
#include <map>
using namespace std;
vector<int> adj[1001];
vector<int> dag;
bool success;
bool visited[1001] = { false };
bool finished[1001] = { false };
int n, m;
void dfs(int cur){
    if( !success ) return;
    visited[cur] = true;
    for( auto next : adj[cur] ){
        if( !visited[next] ){
            dfs(next);
        }
        else if( !finished[next] ){
            success = false;
            return;
        }
    }
    dag.push_back(cur);
    finished[cur] = true;
}
int main(){
    scanf("%d%d",&n,&m);
    while(m--){
        int k; scanf("%d",&k);
        int cur; scanf("%d",&cur);
        adj[0].push_back(cur);
        for( int i = 1 ; i < k ; ++i ){
            int next; scanf("%d", &next);
            adj[cur].push_back(next);
            cur = next;
        }
    }
    success = true;
    dfs(0);
    dag.pop_back();

    if( !success ){
        printf("0");
    }
    else{
        reverse(dag.begin(), dag.end());
        for( auto node : dag ){
            printf("%d\n", node);
        }
    }
    return 0;
}

algoshipda 8년 전 1

순서로 불가능한 경우는 위상정렬이 불가능 한 경우를 말하는 건데, 위상정렬은 그래프에 사이클이 존재하면 불가능합니다.

leechhe 8년 전 0

@algoshipda 답변 감사합니다.

사이클이 존재하는 경우는 finished 배열로 체크를 하였습니다.

finished는 각 dfs(cur)가 끝날 때 true로 세팅합니다. dfs로 탐색을 하다가

1. 이미 방문을 했지만

2. 아직 함수가 종료되지 않은 경우

를 찾았을 때 사이클이 존재한다고 판단했습니다. 혹시 여기에 오류가 있나요?

for( auto next : adj[cur] ){
        if( !visited[next] ){
            dfs(next);
        }
        else if( !finished[next] ){
            success = false;
            return;
        }
    }

algoshipda 8년 전 1

DFS를 한 컴포넌트에 대해서만 돌려서 그런것 같아요.

leechhe 8년 전 0

전체 그래프는 1번부터 시작하는데 그래프를 만들 때 각 PD들의 리스트 시작을 0번 노드와 연결하여 DFS(0)로 하였습니다.

다 탐색할 수 있지 않나요?

int k; scanf("%d",&k);
        int cur; scanf("%d",&cur);
        adj[0].push_back(cur);
        for( int i = 1 ; i < k ; ++i ){
            int next; scanf("%d", &next);
            adj[cur].push_back(next);
            cur = next;
        }

portableangel 8년 전 0

그래프가 연결 그래프가 아니라서 컴포넌트가 여러 개일 때를 말씀하신 듯합니다

portableangel 8년 전 0

그리고 0번 노드에 연결될 노드는 항상 indegree가 0인 노드들만이어야 하지 않을까 싶어요.

leechhe 8년 전 0

@portableangel @algoshipda 해결했습니다 감사합니다 :)

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

문제

문제

출처

ICPC

케이스 질문 드립니다.

leechhe 8년 전 0

algoshipda 8년 전 1

leechhe 8년 전 0

algoshipda 8년 전 1

leechhe 8년 전 0

portableangel 8년 전 0

portableangel 8년 전 0

leechhe 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말