사이클검출2 DFS트리에서 간선의 종류, 사이클 검출 ㅁ방향그래프 dfs를 수행하면 그래프의 모든 간선을 한 번씩은 만나게 된다. 그래프에서 어떤 점에서 dfs를 수행하면 트리가 만들어지는데, 트리를 중심으로 그래프의 모든 간선의 종류를 구분해보면 1. 트리간선 dfs트리를 이루는 간선 2. 순방향 간선 스패닝 트리의 선조에서 자손으로 연결되지만 트리간선이 아닌 간선 3. 역방향 간선 트리의 자손에서 선조로 연결되는 간선. 당연히 트리간선에 포함 안됨. 그래프의 사이클유무 판단할때 사용하는 간선. ( 이 간선이 존재하면 그래프에 사이클 존재 ) 4. 교차간선 그 외의 모든 간선. 선조-자손관계가 아닌 정점들 간 연결된 간선. vector adj[MAX]; int vst[MAX]; //방문순서 기록. -1이면 방문안된것. bool fin[MAX]; int c.. 2020. 2. 13. 사이클 검출 ㅁ 양방향 그래프 https://cses.fi/problemset/task/1669 prv배열과 사이클의 끝점, 시작점을 잘 캐치하면 된다. 양방향 그래프가 주어질 때 사이클이 없으면 IMPOSSIBLE출력, 있으면 아무 사이클이나 사이클을 이루는 정점의 크기와 정점번호들 순서대로 출력 const int MAX = 1e5 + 2; int n, m, prv[MAX], st, en; vector adj[MAX]; bool vst[MAX], fin[MAX]; void dfs(int curr, int pr=0) { vst[curr] = true; for (int next : adj[curr]) { if (!vst[next]) { prv[next] = curr; dfs(next,curr); } //다음 정점이 방.. 2020. 1. 23. 이전 1 다음