방향그래프 사이클1 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 /.. 2019. 12. 5. 이전 1 다음
