Acyclic Decomposition

• 주어진 그래프가 이미 비순환 그래프라면, 그대로 출력하면 된다.
• 주어진 그래프에 사이클이 있다면, 간단한 방법으로 두개의 서브셋으로 분할 가능하다
  • 모든 u→v 에지들을 u>v 인 에지와 u<v 인 에지로 나누어서 두개의 부분그래프로 분할하면 각각은 DAG가 된다.
• 총 시간복잡도는 O(|E|)

"""Solution code for "BOJ 8314. Acyclic Decomposition".

- Problem link: https://www.acmicpc.net/problem/8314
- Solution link: http://www.teferi.net/ps/problems/boj/8314

Tags: [ad hoc]
"""

import sys
from teflib import graph as tgraph


def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]
    edges = [
        [int(x) - 1 for x in sys.stdin.readline().split()] for _ in range(m)
    ]

    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
    if tgraph.is_acyclic(graph):
        print('1')
        print(m, *range(1, m + 1))
        return

    inc_order_edges, dec_order_edges = [], []
    for i, (a, b) in enumerate(edges, start=1):
        if a < b:
            inc_order_edges.append(i)
        else:
            dec_order_edges.append(i)

    print('2')
    print(len(inc_order_edges), *inc_order_edges)
    print(len(dec_order_edges), *dec_order_edges)


if __name__ == '__main__':
    main()

• Dependency: teflib.tgraph.is_acyclic