그래프6 Educational 84 div2 D - Infinite Path (약수, 수론, 후속노드그래프) https://codeforces.com/contest/1327/problem/D 약수를 모두 구하는 건 O(루트n), 전처리 후 O(n^(1/3)) 소인수분해는 필요 없다. 사이클 덩어리들이 주어진다. 사이클에 포함된 u,v에 대해 u->v면 v->u경로가 반드시 있다.(주어진 p 배열이 순열이므로) 번호마다 색이 주어진다. 사이클에서 k번째 후속노드를 가리키는 그래프가 모두 같은 색을 이룰 때 infinite path를 이룬다고 하자. infinite path가 존재하기 위한 k의 최소값을 구해라. 사이클의 크기의 1이아닌 약수 k번째 후속노드를 가리키는 그래프는 쪼개진다. 그 외의 경우 사이클의 순서는 바뀔 수 있지만 구성요소는 바뀌지 않는다. 사이클마다 약수번째 후속노드를 가리키는 그래프가 inf.. 2020. 3. 24. BOJ 5719 - 거의 최단 경로 (다익스트라) https://suuntree.tistory.com/120?category=797985참고 https://www.acmicpc.net/problem/5719 참고 링크에서 설명한 아이디어를 그대로 갖다 사용하면 된다. 최단경로에 포함된 간선을 제외한 그래프에서 최단거리를 구해라 1) 다익스트라https://suuntree.tistory.com/120?category=797985참고 https://www.acmicpc.net/problem/5719 참고 링크에서 설명한 아이디어를 그대로 갖다 사용하면 된다. 출발점 s에서 도착점 e로 갈때, 최단경로에 포함된 간선을 제외한 그래프에서 최단거리를 구해라 1) 다익스트라를 적용해서 dist배열을 초기화 한다. 2) 도착점 부터 역방향 인접배열를 사용해서 모든 .. 2020. 1. 27. 사이클 검출 ㅁ 양방향 그래프 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. codeforces #612 div2 D - Numbers on Tree (그래프, 수학, 구현) https://codeforces.com/contest/1287/problem/D 실패할 조건을 찾은데서 그친 문제. 시험볼 당시엔 좀만 보면 풀 수 있을 것 같다고 생각했지만, 꽤 오래 생각해봐도 못풀었다. 최대크기 2000의 트리가 주어진다. 각 정점마다 a[i]값을 갖는다. (이 값은 주어지지 않는다. 찾아내야 함) 이 때, 각 정점이 루트가되는 서브트리에서 현재 정점의 a값보다 작은 a값을 갖는 정점들의 수를 c값이 주어질때 가능한 a배열을 구해라. 위->아래, 왼쪽->오른쪽 순서대로 각 정점 번호가 1,2,3,4,5이다. (오른쪽 리프노드가 5번정점이다.) 크게 쓰인 수가 a값이고 괄호 안의 값이 c값이다. 1. 실패조건 각 정점을 루트로 하는 서브트리의 크기를 sz[i]라고 하자. 그러면 c[.. 2020. 1. 7. 이전 1 2 다음
