백준 8314 (C++) Acyclic Decomposition

최초 업로드: 2025-09-05 13:01:47

최근 수정 시간: 2025-09-05 13:02:03

게시자: rlatjwls3333

카테고리: 백준

# [Platinum V] Acyclic Decomposition

[문제 링크](https://www.acmicpc.net/problem/8314)

## 문제 설명

Byteman is studying directed graphs. He especially likes graphs which do not contain cycles, since this is a class of graphs in which many problems can be solved easily and effectively. Now he is trying to find a method of representing any directed graph as a sum of acyclic graphs.

For a given directed graph he is trying to find a way to divide the set of its edges into a minimal number of subsets in such a way that the graphs constructed using the respective subsets of edges do not contain cycles. Could you write a program which solves Byteman's problem?

## 입력

The first line of the standard input contains two integers n and m (1 ≤ n, m ≤ 100,000), denoting the number of vertices and the number of edges in the graph, respectively. The vertices are numbered from 1 to n. Each of the following m lines contains a description of one edge of the graph as a pair of integers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi). Such a pair denotes a directed edge of the graph from the vertex ai to the vertex bi. You may assume that the graph does not contain multiple edges.

## 출력

The first line of the standard output should contain a single integer k - the minimal number of acyclic graphs in any decomposition of the graph. Each of the following k lines should contain a description of one element of the decomposition, starting with an integer li denoting the number of edges in the ith element. It should be followed by an increasing sequence of li numbers of edges belonging to the ith element of the decomposition. The edges are numbered from 1 to m in the order in which they appear in the input. Each edge should be present in exactly one element of the decomposition.

If there are multiple correct solutions, your program should output any one of them.

## 풀이
사이클이 존재하지 않는 경우 나눌 필요가 없고, 사이클이 존재하면 사이클로 만드는 간선 몇 개만 다른 그룹으로 보내면 두 그룹으로 분할할 수 있다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MAX = 100'001;

bool visited[MAX];
vector<vector<int>> conn(MAX);

bool dfs(int cur) {
    visited[cur]=true;

for(int next:conn[cur]) {
        if(visited[next] || !dfs(next)) return false;
    }
    visited[cur]=false;
    conn[cur].clear();
    return true;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;

vector<vector<int>> res(2);
 for(int i=1;i<=m;i++) {
 int a, b; cin >> a >> b;
 conn[a].push_back(b);
 if(a<b) res[0].push_back(i);
 else res[1].push_back(i);
 }

bool chk=true;
 for(int i=1;i<=n;i++) chk &= dfs(i);
 if(chk) {
 cout << "1\n" << m;
 for(int i=1;i<=m;i++) cout << ' ' << i;
 return 0;
 }

if(res[0].empty()) swap(res[0], res[1]);
    if(res[1].empty()) res.pop_back();

if(res.size()==2 && res[0].size()>res[1].size()) swap(res[0], res[1]);

cout << res.size() << '\n';
 for(auto &group : res) {
 cout << group.size();
 sort(group.begin(), group.end());
 for(int e : group) cout << ' ' << e;
 cout << '\n';
 }
}
```