Problem

In a power grid network composed of n transmission towers connected in a tree structure via wires, you are tasked with dividing the network into two parts by cutting one of the wires. The goal is to make the number of transmission towers in each part as equal as possible. Given the number of towers n and the wire connections wires, your function solution should return the smallest difference in the number of transmission towers between the two resulting networks after one cut.

Constraints

n is a natural number between 2 and 100, inclusive.
wires is a two-dimensional array of integers with a length of n-1.
Each element in wires is a pair [v1, v2], indicating that the transmission tower v1 is connected to tower v2 via a wire.
1 ≤ v1 < v2 ≤ n.
The network always forms a single tree structure.

Example

n	wires	result
9	[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]	3
4	[[1,2],[2,3],[3,4]]	0
7	[[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]	1

Explanation of Examples

Example 1:
- There are 9 towers connected by 8 wires forming a tree. By choosing the optimal wire to cut, the difference in the number of towers between the two resulting networks can be minimized to 3.
Example 2:
- With 4 towers connected in a straight line, cutting any of the wires results in two parts with an equal number of towers, resulting in a difference of 0.
Example 3:
- A network of 7 towers can be split by the optimal wire cut to achieve a minimum tower difference of 1 between the two networks.

How to Approach?

Step1: Initialize variables in loop

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65


import java.util.ArrayList;
import java.util.List;

public class Solution {
    List<List<Integer>> adjList = new ArrayList<>();
    boolean[] visited;
    int totalTowers;
    int minDifference = Integer.MAX_VALUE;

    public int solution(int n, int[][] wires) {
        totalTowers = n;
        visited = new boolean[n + 1];
        
        // Initialize adjacency list for all nodes
        for (int i = 0; i <= n; i++) {
            adjList.add(new ArrayList<>());
        }
        
        // Construct the tree using adjacency list
        for (int[] wire : wires) {
            int v1 = wire[0];
            int v2 = wire[1];
            adjList.get(v1).add(v2);
            adjList.get(v2).add(v1);
        }
        
        // Try cutting each wire and calculate the difference
        for (int[] wire : wires) {
            int v1 = wire[0];
            int v2 = wire[1];
            
            // Remove the connection (cut the wire)
            adjList.get(v1).remove(Integer.valueOf(v2));
            adjList.get(v2).remove(Integer.valueOf(v1));
            
            // Reset visited array for new DFS
            visited = new boolean[n + 1];
            int towersInSubtree = countTowersDFS(v1);
            
            // Calculate difference in towers and update minDifference
            int difference = Math.abs(totalTowers - 2 * towersInSubtree);
            minDifference = Math.min(minDifference, difference);
            
            // Reconnect the wire
            adjList.get(v1).add(v2);
            adjList.get(v2).add(v1);
        }
        
        return minDifference;
    }

    private int countTowersDFS(int node) {
        visited[node] = true;
        int towersCount = 1; // Count the current node
        
        // Recurse on all adjacent nodes
        for (int adjNode : adjList.get(node)) {
            if (!visited[adjNode]) {
                towersCount += countTowersDFS(adjNode);
            }
        }
        
        return towersCount;
    }
}