프로그래머스. 전력망을 둘로 나누기

https://programmers.co.kr/learn/courses/30/lessons/86971#

코딩테스트 연습 - 전력망을 둘로 나누기

 

다음과 같은 2차원 벡터에 각 노드별로 이동할수 있는 노드를 푸쉬해 관계를 형성한다.

vector<vector<int> edges(110, vector<int>(0))

 

주어진 wires 배열을 순회하면서 관계를 하나씩 끊어본다.

관계를 끊는다는 것은 하나의 노드에서 dfs로 탐색할때 관계가 끊긴 노드는 이동하지 않도록 하는 것이다.

 

예를들어 wires[0] = {1,3}일때면 1과 3의 관계를 끊어보고,

1에서부터 dfs를 돌아보고, 3에서부터도 돌아봐서 각각 방문할수 있는 노드의 수의 차를 구하면 된다.