devlog

그래프에서 사이클이 존재하는지 여부는 dfs 를 사용해서 직관적으로 찾을 수 있다. 일반적인 그래프의 코드를 살펴보도록 하자 static void dfs(int v) { visit[v] = true; for(int u : adj[v]) { if(visit[u]) continue; dfs(u); } } v 라는 정점을 기준으로 dfs 를 수행한다고 했을 때 dfs(v) 가 끝나기 전에 v 를 재방문하는 일이 생기면 사이클이 존재함을 알 수 있다. 아래의 코드는 dfs 를 이용한 사이클 존재 여부를 확인하는 코드이다. static boolean cycle = false; static boolean[] visit = new boolean[n+1]; static boolean[] finished = new bo..