[Baekjoon - 8314] Acyclic Decomposition

난이도: Platinum V

 

태그

• Directed Acyclic Graph
• Topological Sort
• Depth-First Search

 

풀이

1. 입력된 그래프가 이미 DAG라면?

이미 사이클이 없으므로 굳이 더 나눌 필요가 없습니다.

이 때의 답은 1이 됩니다.

 

2. 입력된 그래프가 DAG가 아니라면?

항상 2개로 나눌 수 있습니다.

간단한 방법은, 정점 번호를 기준으로 v < w인 간선과 v > w인 간선으로 나누는 방법이 있습니다.

 

3. 코드

vector<pi2> adj[100020];
 
bool chk[100020];
int ord[100020], ont = 0;
void dfs(int now){
    chk[now] = 1;
    for (pi2 p : adj[now]){
        int nxt = p.fr;
        if (!chk[nxt]){ dfs(nxt); }
    }
    ord[now] = ++ont;
}
 
void Main(){
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int v, w; cin >> v >> w;
        adj[v].push_back({w, i});
    }
    for (int i = 1; i <= n; i++){
        if (!chk[i]){ dfs(i); }
    }
    vector<int> v1, v2;
    for (int v = 1; v <= n; v++){
        for (pi2 p : adj[v]){
            int w = p.fr, i = p.sc;
            (ord[v] > ord[w] ? v1 : v2).push_back(i);
        }
    }
    sort(all(v1)); sort(all(v2));
    if (v1.size() == m){
        cout << 1 << endl;
        cout << v1.size() << ' '; for (int x : v1){ cout << x << ' '; }
    }
    else{
        cout << 2 << endl;
        cout << v1.size() << ' '; for (int x : v1){ cout << x << ' '; } cout << endl;
        cout << v2.size() << ' '; for (int x : v2){ cout << x << ' '; }
    }
}