[Java] leetcode 2316. Count Unreachable Pairs of Nodes in an Undirected Graph

문제

https://leetcode.com/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/description/

Count Unreachable Pairs of Nodes in an Undirected Graph - LeetCode

무방향 그래프가 주어졌을떄, 다른 집합들의 orderedPair 순서쌍 개수를 구하는 문제 

풀이

풀이 알고리즘은 다음과 같다. 

1. 이어져있는 그래프들의 개수를 탐색하고, 리스트에 추가한다.
2. 선형 탐색으로 다음을 수행한다. 
   
   1. 전체 원소의 수 E , i번쨰 그룹의 원소 개수 k 
   2. 각 반복문마다 k * (E - k ) 한 값을 누적합하고 E -= k 를 수행.
3. 정답을 리턴한다.

순서 상관 없이 두 개의 원소를 뽑는 조합으로 문제를 풀었다.

알고리즘 2-2 에서  E -= k 를 수행하는 이유는 i번째에 원소를 사용했으면 전체 원소에서 그만큼 값을 뺴 줘야 하기 때문이다. 

 

코드

자바

class Solution {
    ArrayList<ArrayList<Integer>> g ;
    public long countPairs(int n, int[][] edges) {
        g = new ArrayList<>();
        for(int i = 0 ;i < n ;i++)
            g.add(new ArrayList<>());
        
        for(int x[] : edges){
            g.get(x[0]).add(x[1]);
            g.get(x[1]).add(x[0]);
        }
        boolean v[] = new boolean[n];
        ArrayList<Integer> nodeSetList = new ArrayList<>();
        long elementSize = 0;
        for(int i = 0 ;i < n ;i++){
            if(!v[i]){
                v[i] = true;
                int val = dfs(i, v);
                elementSize += val;
                nodeSetList.add(val);
            }
        }
        
        int size = nodeSetList.size();
        
        long ret = 0;
        for(int i = 0 ;i < size-1; i++){
            elementSize -= nodeSetList.get(i);
            ret += nodeSetList.get(i) * elementSize;
        }
        return ret;
    }
    public int dfs(int start , boolean[]v){
        int cnt = 1;
        for(int nv : g.get(start)){
            if(!v[nv]){
                v[nv] = true;
                cnt += dfs(nv, v);
            }
        }
        return cnt;
    }
}