생각보다 인과를 따져나가니 별거 없던 문제였다.
에디토리얼에서 소스코드를 보고 이를 증명해보자.
우리가 추가해야하는 엣지를 간접 엣지라고 하자(간접적으로 연결되어 있다는 뜻)
그리고 기존에 존재하던 엣지를 직접 엣지라고 부르자.
먼저, 직접 엣지는 문제가 주어질 때 중복없이 모두 주어짐이 보장되어있다.
그리고 각 노드마다 bfs나 dfs를 진행하면서 직접연결, 간접연결되어있는 모든 노드의 개수를 구한다.
이 때, bfs를 출발하는 노드를 x라고 했을 때,
x와 직접연결 되어있는 노드의 개수는 직접 연결되어있는 노드의 개수와 같다.
그리고 직접 연결되어 있는 노드들은 bfs를 진행하면서 모두 구할 수 밖에 없다.
그리고 문제에서 간접연결 되어있는 a와 c를 잇게하는 엣지를 추가하라고 했는데,
이는 a와 c를 직접연결 시키는 엣지를 추가하라는 말과 같다.
즉 bfs를 수행하며 구한 모든 노드의 개수는
직접 엣지의 개수(M)개와 간접 연결 되어있는 노드를 직접연결 시키는 노드의 개수와 같다.
이 개수를 모두 구한 후 M개를 빼면 답이다.