그래프이론1 codeforces #581 div2 C - Anna, Svyatoslav and Maps ( 플로이드 ) https://codeforces.com/contest/1204/problem/C 루프가 없는 단방향 그래프에 대해, 임의의 경로를 입력으로 주고, 그 입력의 처음과 끝은 그대로이지만 경로는 똑같을 수 밖에 없는 정점의 배열을 출력하는 문제. (물론 그 배열의 크기는 최소가 되도록.) 위와 같은 그래프와 입력이 1 2 3 4 1 2 3 4 일떄 출력은 1 2 4 2 4 이다. 1 3 4 2 4가 안되는 이유는 3번 정점을 방문하면 입력한 경로에서 벗어나기 때문이다. 풀이) 1. 첫번째 정점과 마지막 정점은 항상 출력해야 한다. 그리고 int arr[]에 입력 경로가 담겨있고, vector ans에 출력할 정답을 담는다고 하자. (pair엔 정점번호, 입력배열에서의 인덱스) 여기서 인덱스를 저장하는 것은 .. 2019. 11. 4. 이전 1 다음
