https://school.programmers.co.kr/learn/courses/30/lessons/86971
import java.util.*;
class Solution {
public int solution(int n, int[][] wires) {
ArrayList<ArrayList<Integer>> map = new ArrayList<ArrayList<Integer>>();
for(int i = 0; i < n+1; ++i)
map.add(new ArrayList<Integer>());
for(int i = 0; i < wires.length; ++i)
{
int a = wires[i][0];
int b = wires[i][1];
map.get(a).add(b);
map.get(b).add(a);
}
int answer = 1000000;
for(int i = 0; i < wires.length; ++i)
{
int a = wires[i][0];
int b = wires[i][1];
int acount = bfs(a, n, map, b);
int bcount = bfs(b, n, map, a);
answer = Math.min(answer, Math.abs(acount-bcount));
}
return answer;
}
public int bfs(int start, int n, ArrayList<ArrayList<Integer>> map, int cut)
{
int count = 1;
Queue<Integer> que = new LinkedList<Integer>();
boolean[] visit = new boolean[n+1];
que.add(start);
visit[start] = true;
while(que.isEmpty()==false)
{
ArrayList<Integer> cur = map.get(que.poll());
for(int nei : cur)
{
if(nei == cut)
continue;
if(visit[nei])
continue;
visit[nei] = true;
que.add(nei);
count++;
}
}
return count;
}
}