사이클1 cf #656 div3 E - Directing Edges(위상정렬, 사이클 유무) https://codeforces.com/contest/1385/problem/E 방향그래프와 무향그래프가 섞인 그래프에서 위상정렬을 구해야 해서 헷갈렸다. 위상정렬 결과로 사이클 판단하는 방법도 숙지해 뒀어야 하는 문제 정점u,v사이엔 최대 하나의 무향또는 유향간선만 존재하는 그래프가 주어진다. 유향간선을 적절히 조정해서 accyclic그래프를 만들 수 있다면 그 간선들을 출력하라 손으로 좀 그리다보면 유향간선만 가지고 사이클이 존재하지 않는다면 항상 정답이 존재함을 알 수 있다. 유향간선 기준 ind로 topological sort를 한 순서벡터로 각 정점마다 순서를 매긴다. 유향간선 u->v 중 rank[u]>rank[v]인 경우가 존재하면 사이클이 있다는 것 의미함. 사이클이 없다면 ,모든 간선을.. 2020. 7. 20. 이전 1 다음