dfs4 BOJ 15587 - Cow at Large (multisource bfs, dfs) https://www.acmicpc.net/problem/15587 트리가 주어진다. bessie의 위치 k가 주어진다. bessie를 쫓는 farmer들은 리프노드에서 출발한다. 모두 한번에 한칸씩 움직일 수 있을 때, bessie가 리프노드에 도달하지 못하도록 하려면 최소 몇명의 farmer가 필요한가? 모든리프노드 에서부터 멀티소스 플러드필을 해서 dist를 갱신해준다. dist[u] : u정점까지 어떤 farmer가 도착하기 까지의 시간. bessie의 초기 위치 k부터 dfs를 하며 현재 위치가 u 이동거리 d일 때, dist[u] n >> k; for (int i = 0, u, v; i > u >> v; adj[u].push_back(v); adj[v].p.. 2020. 2. 19. 사이클 검출 ㅁ 양방향 그래프 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. Educational codeforces 67 div2 E - tree painting (dfs, dp, rerooting, tree) https://codeforces.com/contest/1187/problem/E 항상 궁금했던 그래프+dp 유형. editorial피셜로 기본문제라고 한다. https://suuntree.tistory.com/126?category=805933 트리에서 모든정점 사이즈 선형시간에 구하는 법 트리가 주어진다. 임의의 정점 하나를 선택한다. 그 정점을 루트로 취급할 때 그 서브트리의 모든 정점들의 size합을 구한다. 그 값 중 최대를 구해라. dp[u] : u를 트리의 루트로 봤을 때 모든 정점의 사이즈 합 위 예시와 같이 루트를 바꿨을 때 dp값이 바뀔 여지가 있다. dp값이 바뀐다면 참조투명하지 않다는 것인데, rerooting 테크닉을 사용하여 이를 극복하는 것에 유념하여 보면 된다. 일단 직관적으.. 2020. 1. 21. Educational round #72 div2 D - Coloring Edges (방향그래프 사이클) https://codeforces.com/contest/1217/problem/D (editorial 풀이) 방향그래프가 주어진다. 정점(n)과 간선(m)의 최대는 각각 5000이다. 각 간선에 최소한의 색(k)을 칠해서 같은 색의 간선끼리 cycle이 생기지 않도록 하는 k와 그때 간선의 색을 모두 출력하는 문제다. editorial의 설명 -> 간선 (u,v)가 back edge : if there is a path from v to u by edges from dfs tree 문제 풀땐 if there is a 'edge' from v to u by edges from dfs tree 로 생각하도록 하겠다. dfs tree를 그리고 back edge를 추가한 그래프를 떠올려보자. 다음은 1, 2 /.. 2019. 12. 5. 이전 1 다음
