There are n
cities numbered from 0
to n - 1
and n - 1
roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.
Roads are represented by connections
where connections[i] = [ai, bi]
represents a road from city ai
to city bi
.
This year, there will be a big event in the capital (city 0
), and many people want to travel to this city.
Your task consists of reorienting some roads such that each city can visit the city 0
. Return the minimum number of edges changed.
It's guaranteed that each city can reach city 0
after reorder.
0번에서 n - 1
번까지 번호가 매겨진 n
개의 도시와 서로 다른 두 도시 간에 이동할 수 있는 한 가지 방법만 있는 n - 1
개의 도로가 있습니다(이 네트워크는 트리 형태를 이룹니다). 작년에 교통부는 도로가 너무 좁기 때문에 도로를 한 방향으로 정하기로 결정했습니다.
도로는 connections
에 의해 표현되며 connections[i] = [ai, bi]
는 도시 ai
에서 도시 bi
로의 도로를 나타냅니다.
올해는 수도(도시 0
)에서 큰 행사가 열릴 예정이며, 많은 사람들이 이 도시로 여행하고자 합니다.
당신의 임무는 몇몇 도로의 방향을 재설정하여 각 도시가 도시 0
을 방문할 수 있도록 하는 것입니다. 변경해야 할 최소한의 도로 수를 반환하세요.
각 도시가 재정렬 후에 도시 0
에 도달할 수 있다는 것이 보장됩니다.
2 <= n <= 5 * 10^4
connections.length == n - 1
connections[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
public class Solution {
public int minReorder(int n, int[][] connections) {
// 각 노드에서 출발하는 간선 리스트를 저장할 그래프 초기화
List<List<int[]>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
// 각 연결을 그래프에 추가
for (int[] connection : connections) {
int from = connection[0];
int to = connection[1];
graph.get(from).add(new int[] { to, 1 }); // 방향성 있는 간선
graph.get(to).add(new int[] { from, 0 }); // 방향성 없는 간선
}
boolean[] visited = new boolean[n];
return dfs(0, graph, visited);
}
private int dfs(int node, List<List<int[]>> graph, boolean[] visited) {
visited[node] = true;
int count = 0;
for (int[] edge : graph.get(node)) {
if (!visited[edge[0]]) {
count += edge[1]; // 방향성 있는 간선일 경우 카운트 증가
count += dfs(edge[0], graph, visited);
}
}
return count;
}
}