Boomerangs

• 잘 관찰해보자.. 케이스를 그려보면서 생각해보면 몇가지 기준들이 떠오른다. 가장 기본적인것은 리프노드에 붙은 엣지부터 부메랑에 추가시켜야 한다는 것이다. 그리고 어떤 엣지를 부메랑에 사용하기로 했다면, 그 엣지를 제거한 뒤에 만들어지는 리프노드를 또다시 우선적으로 고려해주면 된다.
• 잘 정리하면.. 트리인 경우는 이런식으로 될것이다. bottom-up으로 노드를 순회한다고 하자. 현재 노드 u가 자식 노드들 c(1),…,c(n) 을 갖는다면 <c(i),u,c(i+1)> 들의 부메랑을 만든다. 만약 자식이 홀수개라서 한개가 남는다면 부모노드 p를 포함해서 <p,u,c(n)>의 부메랑을 추가로 만들고, u를 p의 자식노드에서 제거한다.
• 일반 그래프에서도 비슷하다. 그래프를 트리처럼 펼쳐서 똑같은 방식을 사용하면 된다. 그래프를 순회하면서 dfs 스패닝 트리와 비슷한 개념으로 트리가 생긴다고 생각하면 되는데, 노드를 여러번 방문해도 상관 없지만, 모든 엣지를 한번씩 방문하도록 해야 한다.
• 큰 방법은 이게 전부인데, 세부 구현에서 좀 신경써줄 필요가 있다. dfs로 모든 엣지들을 한번씩 방문하기 위해서, 방문한 엣지들을 저장하는 visited_edges 셋을 만들어서, 엣지를 하나 건너갈때마다 visited_edges 에 추가하고, 방문한 노드에서 다음 방문할 노드들을 찾기 위해서 엣지들 중에서 visited_edges에 포함 안된 엣지들만 골라서 넘어가는 방식으로 처리했더니 시간초과가 나왔다.
• 이렇게 하면 한 노드를 여러번 방문할 수가 있는데, 그때마다 연결된 엣지들을 다 체크해봐야 하니까, 시간 복잡도가 일반 dfs보다 커지게 된다.
• (예전에 오일러투어 관련 문제들을 풀면서도 이런 고민을 했었던것 같은 기억이 든다;)
• 해결 방법 한가지는, 아예 그래프를 set으로 만들어서, 엣지를 지나갈때마다 그래프에서 그 엣지와 역방향 엣지를 삭제해버리는 것이다. 코드 작성방법에 따라서 이터레이터가 무효화되는것을 피하기 위해서 좀 신경써야 할수도 있지만 속도는 빠르게 돌아간다.
• 다른 방법은, 이미 방문한 노드를 직접적으로 다시 방문하지는 않는 대신에, 노드를 빠져 나갈때 연결된 엣지들중에서 방문 안한 엣지들을 처리해주는 것이다. 이것도 개념적으로는 어렵지 않지만 실수를 안하려면 코딩에 좀 신경 써야 한다. (사실 dfs를 재귀로 구현하면 간단하다.. 비재귀로 풀어서 처리하려니 헷갈려지는것 ㅜㅜ)
• 두가지 방법 다 O(V+E)로 처리가 되고, 시간도 700ms대로 거의 차이가 안난다. 여기에 올린 코드는 두번째 방법.
• 그리고 이것 말고도 다른 이유로 WA를 여러번 받았는데.. 그래프가 연결그래프가 아닐수도 있다. 모든 노드에 대해서 그 노드를 출발점으로 dfs를 다 돌려서 처리해야 한다.

"""Solution code for "BOJ 16583. Boomerangs".

- Problem link: https://www.acmicpc.net/problem/16583
- Solution link: http://www.teferi.net/ps/problems/boj/16583

Tags: [DFS]
"""


import sys
from teflib import graph as tgraph


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    graph = [set() for _ in range(N)]
    for _ in range(M):
        u, v = [int(x) for x in sys.stdin.readline().split()]
        graph[u - 1].add(v - 1)
        graph[v - 1].add(u - 1)

    answers = []
    prev = [None] * N
    children = [[] for _ in range(N)]
    for source in range(N):
        for u, is_discovering in tgraph.full_dfs(graph, source, prev=prev):
            p = prev[u]
            if is_discovering:
                for v in graph[u]:
                    if v != p and prev[v] is not None:
                        children[u].append(v)
            else:
                children_u = children[u]
                for i in range(0, len(children_u) - 1, 2):
                    answers.append((children_u[i], u, children_u[i + 1]))
                if p != u:
                    if len(children_u) % 2 == 1:
                        answers.append((p, u, children_u[-1]))
                    else:
                        children[p].append(u)

    print(len(answers))
    for answer in answers:
        print(*(x + 1 for x in answer))


if __name__ == '__main__':
    main()

• Dependency: teflib.graph.full_dfs