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

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

 

문   제 : 

n개의 정점이 주어진다. 

정점끼리의 연결을 표시한 배열 edges[i][j] 가 주어진다. 

정점 i와 정점 j가 연결되어있다는 뜻이며 양방향성이다.

 

이어지지 않은 정점들의 쌍의 개수를 구하여라.

 

 

Constraint

{ 1 <= n <= 10^5 }

{ 1 <= edges.length <= 2 * 10^5) }

{ edges[i].length == 2 }

 

You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.

Return the number of pairs of different nodes that are unreachable from each other.

 

Example )

Input: n = 3, edges = [[0,1],[0,2],[1,2]]
Output: 0
Explanation: 
There are no pairs of nodes that are unreachable from each other. Therefore, we return 0.

=======================================

Input: n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
Output: 14
Explanation: 
There are 14 pairs of nodes that are unreachable from each other:
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]].
Therefore, we return 14.

 

 

---

접   근 : 

DFS를 활용한 노드 방문 처리

---

해   결 : 

n개의 크기를 가진 visited배열을 선언한다. - n번 노드가 방문되었는지 안되었는지를 나타내는 배열이다.

List 을 원소로 가지는 List를 n개 선언한다. - n번 노드와 연결된 노드들을 자식으로 가지는 List이다.

 

List를 초기화 해준다. -> edges를 참조하여 연결된 노드들을 선언한 List에 등록해준다.

이때까지 리턴받은 값을 누적해서 저장하는 변수 nvis를 선언해준다.

 

방문이 안된 노드이면 DFS를 수행한다.

그리고 리턴 받은 값 * nvis res에 계속 누적합해준다.

nvis를 최신화해준다.

 

 

DFS :

인자로 넘어온 node를 방문처리해준다.

이 node와 연결된 노드의 개수를 표시하는 변수 connectNum을 1로 선언한다.

 

그리고 node와 연결된 다른 node들 에게도 다시 재귀(DFS)를 통해 방문처리를 해준다.

connectNum 을 리턴한다.

결과적으로, 연결되어있는 노드들의 개수가 리턴된다. 

---

결   과  :

class Solution {
    public long countPairs(int n, int[][] edges) {
        long res=0;

        List<List<Integer>> nodes = new ArrayList<>();
        int visited[] = new int[n];
        Arrays.fill(visited, 0);

        for(int i=0; i<n; i++) {
            nodes.add(new ArrayList<>());
        }

        for(int i=0; i<edges.length; i++){
            int start = edges[i][0];
            int end = edges[i][1];

            nodes.get(start).add(end);
            nodes.get(end).add(start);
        }
        
        long nvis = 0;
        for(int i=0; i<n; i++){
            if(visited[i] == 0) {
                long a = dfs(i, nodes, visited);
                res += a * nvis;
                nvis += a;
            }
        }
        return res;

    }
    public long dfs(int node, List<List<Integer>> nodes, int visited[]){
        visited[node] = 1;
        int connectNum = 1;

        for(int i : nodes.get(node)){
            if(visited[i] == 0)
                connectNum += dfs(i, nodes, visited);
        }
        return connectNum;
    }
}