[LeetCode] 1971. Find if Path Exists in Graph c++

• 문제

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex source to vertex destination.

Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.

 

출처 : https://leetcode.com/problems/find-if-path-exists-in-graph/

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
- 0 → 1 → 2
- 0 → 2

 

 

• 문제 해결

Union-Find algorithm을 이용해서 푸는 문제입니다.

알고리즘 설명은 아래 링크에 적어두었습니다.

[Algorithm] Union-Find algorithm

 

1. 노드의 개수 만큼 배열 선언

2. 각 노드의 루트노드를 가르키는 배열 선언, 초기화(parent 배열) = unf벡터

3. 주어진 조건에 맞게 각 노드의 parent 배열 값은 그 노드가 가르키는 노드로 변경

4. Find(x) : 루트 노드를 찾는 함수이므로 루트에 도달할 때까지 부모 노드를 찾아 올라간다.

5. Union(x) : x 및 y를 포함하는 부분집합을 나타내는 트리를 다른 것의 부트리로 만든다.

class Solution {
public:
    
    vector<int> unf;
    
    int unfFind(int node){
        if( unf[node] == node)
            return node;
        
        return unf[node] = unfFind(unf[node]);
    }
    
    void Union(int a, int b){
        a = unfFind(a);
        b = unfFind(b);
        if( a!= b){
            unf[a] = b;
        }
    }
    
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        
        unf.resize(n);
        
        for(int i = 0; i < n; i++){
            unf[i] = i;
        }
       
        for(const auto &it : edges){
            Union(it[0], it[1]);
        }
        return unfFind(source) == unfFind(destination);
    }
};