https://www.acmicpc.net/problem/24493
24493번: Cereal 2
Print the minimum number of cows that go hungry, followed by any permutation of $1\ldots N$ that achieves this minimum. If there are multiple permutations, any one will be accepted.
www.acmicpc.net
반례가 자꾸 나와서 12번 제출해서 맞은 문제
시리얼을 정점, 소를 간선으로 보고 (f[i], s[i])를 이어준다. (간선 방향은 상관 없음. 일단 무방향으로 다 이어준다.)
다른 연결요소들 끼리는 배치 순서가 상관이 없으므로 각 연결요소 안에서만 생각하면 됨.
1) 간선 개수(e) = 정점 개수(v) - 1
루트를 아무거나 잡고 dfs 돌리면 간선에서 f[i], s[i] 순서가 어떻든 방문한 간선 순서대로 배치하면 시리얼을 다 먹을 수 있다.
2) e >= v
시리얼을 아무리 많이 먹어도 v개 초과해서는 먹을 수 없다. dfs트리 만들 때 back edge하나 발견하면 그 edge를 먼저 배치하고 그 edge에 해당하는 f[i]를 루트로 잡고 dfs 돌려서 방문한 간선 순서대로 배치하면 된다.
틀렸던 이유
1. N이랑 M을 헷갈려서 vector 크기를 잘못 잡음. vector도 vector v1 다음에 vector v2를 선언하면 v1 인덱스를 넘어갔을때 v2에 채워지는걸 처음 앎.
2. 처음에 back edge에서 f[i]말고 s[i]를 루트로 잡으면 되는 걸로 착각함.
3. back edge를 먼저 배치했으면 dfs 돌릴때 거기다 표시를 하고 방문을 안해야 되는데 해버림.
4. f[i] = s[j], f[j] = s[i]인 경우가 있을 수 있다는걸 간과함. next = prev여도 아직 방문을 안한 간선이기에 back edge가 될 수 있음.