무방향그래프 사이클1 codeforces #580 div2 D - Shortest Cycle (무방향그래프 사이클, 비둘기집) https://codeforces.com/contest/1206/problem/D undirected graph이고, 최대 1e5개의 정점에 대해 만들어지는 사이클 크기의 최소값을 구하는 문제이다. 오픈카톡에 따르면 무방향그래프에서 사이클을 모두 구하는 것에 대한 알고리즘은 매우 어렵다. ( 불가능하지 않냐고 물어보는 사람도 있었다. ) 하지만 지금 문제에선 사이클 크기의 최소값을 구하는 것이므로 알고리즘을 짤 수 있다. 1) 사이클 크기의 최소값 구하기 서로 연결돼 있는 i,j에 대해, 그 간선을 끊었을 때 i~j의 경로 길이 + 1(자기자신)이 사이클 크기이다. 이를 모든 간선에 대해 적용하며 mn값을 갱신해 나가면 된다. 즉, adj[i][j]=adj[j][i]=0 -> mn = min( dist[.. 2019. 11. 13. 이전 1 다음