Educational round #72 div2 D - Coloring Edges (방향그래프 사이클)

https://codeforces.com/contest/1217/problem/D

 

(editorial 풀이)

 

<문제설명>

방향그래프가 주어진다. 정점(n)과 간선(m)의 최대는 각각 5000이다.

 

각 간선에 최소한의 색(k)을 칠해서 같은 색의 간선끼리 cycle이 생기지 않도록 하는 k와 그때 간선의 색을 모두 출력하는 문제다.

 

<개념설명>

editorial의 설명 -> 간선 (u,v)가 back edge :  if there is a path from v to u by edges from dfs tree

문제 풀땐 if there is a 'edge' from v to u by edges from dfs tree 로 생각하도록 하겠다.

 

<풀이>

dfs tree를 그리고 back edge를 추가한 그래프를 떠올려보자.

 

다음은 1, 2 / 2,3 / 3,1 간선에 대한 예이다. 빨간 선이 back edge이다.

 

 

이런식으로 사이클이 형성되는 그래프의 경우, back edge가 반드시 포함된다. 

반대로 back edge로 인해 사이클이 생성되는 것이라고 생각할 수 있다.

 

그런 back edge의 색을 '2' 나머지 간선의 색을 '1'로 칠해주는 것이 정답이다.

(사이클이 존재할 때와 사이클이 존재하지 않을 때로 나누면 된다.)

 

이 back edge는 dfs 하면서 finished되지 않은 정점을 만났을 때 검출할 수 있다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
typedef pair<int, int> P;  //to, 간선번호
const int MAX = 5e3+5;

int n, m;
vector<P> adj[MAX];
bool visited[MAX], finished[MAX];
bool hasCyc;
int color[MAX];

void dfs(int curr) {
	visited[curr] = true;
	for (P p : adj[curr]) {
		int next = p.first, id = p.second;
		if (!visited[next]) {
			dfs(next);
		}
		else if (!finished[next]) {
			hasCyc = true;
			color[id] = 2;
		}
	}
	finished[curr] = true;
}

int main() {
	cin >> n >> m;
	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		adj[u].push_back({ v, i });
	}

	fill(color, color + MAX, 1);

	for (int i = 0; i < n; i++)
		if (!visited[i])
			dfs(i);

	cout << (hasCyc ? 2 : 1) << '\n';
	for (int i = 0; i < m; i++)
		cout << color[i] << " ";
	cout << '\n';
}

 

 

<ps>

scc문제인줄 알았는데 전혀 아니었다.

 

방향그래프의 사이클에 관한 문제는 항상 새롭다.

 

방향그래프의 사이클과 back edge의 관계 알 수 있었던 좋은 기회였던 것 같다.