밸만포드2 사이클 검출 ㅁ 양방향 그래프 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. 벨만포드, SPFA 시작점을 정해줬을 때, 최단경로 알고리즘. 가중치가 음수여도 가능하다 *모든 간선을 돌면서 그에 속하는 정점에 대한 dist를 초기화할 수 있다면 초기화 해주는 작업을 정점개수-1만큼 반복한다. O(EV) 필요한 것: int dist[MAX]{0} vector adj[MAX]; //혹은 vector edge 일반적인 코드. 음의 사이클 검출방법 int main() { int N, M, dist[MAX], st, en; fill(dist, dist + N, INF); vector adj[MAX]; dist[st] = 0; bool minusCycle = false; for (int k = 0; k < N; k++) { // (N-1)번의 루프, N번째루프에 갱신되면 음의사이클존재 //이하 두개의 for문 .. 2019. 8. 18. 이전 1 다음