[LeetCode] 1579. Remove Max Number of Edges to Keep Graph Fully Traversable

https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/description/

leetcode - Remove Max Number of Edes to Keep Graph Fully Traversable

문제 유형 : 유니온-파인드, 그리디

문제 난이도 : Hard

 

문제

Alice and Bob have an undirected graph of n nodes and three types of edges:

• Type 1: Can be traversed by Alice only.
• Type 2: Can be traversed by Bob only.
• Type 3: Can be traversed by both Alice and Bob.

Given an array edges where edges[i] = [typei, ui, vi] represents a bidirectional edge of type typei between nodes ui and vi, find the maximum number of edges you can remove so that after removing the edges, the graph can still be fully traversed by both Alice and Bob. The graph is fully traversed by Alice and Bob if starting from any node, they can reach all other nodes.

Return the maximum number of edges you can remove, or return -1 if Alice and Bob cannot fully traverse the graph.

 

Alice와 Bob은 N개의 노드의 무방향 그래프와 3가지 타입의 간선을 가진다:

타입1: Alice만 이동가능한 길.

타입2: Bob만 이동가능한 길.

타입3: 둘다 이동가능한 길

 

edges[i] = [type_i, u_i v_i]로 구성된 무방향 그래프의 간선이 주어진다.

[타입, 정점1, 정점2]로, 정점1과 2 사이에 <타입>의 간선을 가진다.

그래프는 최대한 많은 간선을 없애고도 순회될 수 있어야 한다.

 

없앨 수 있는 최대 간선의 수를 구하시오.

순회가 불가능하다면 -1을 반환하시오.

 

풀이

유니온-파인드를 이용하여 풀 수 있다.

유니온파인드를 위한 클래스를 하나 만든다.

필드는 다음과 같다:

vector<int> parent; //자신이 소속된 disjoint set의 최종 루트를 말한다.

vector<int> rank; //disjoint set에서의 자신의 rank를 말한다.

 

int find(int x) // x의 최종 루트를 반환한다. 중간 과정에서, parent를 재귀함수를 통해 업데이트하여, 루트까지의 경로 압축이 가능하다. 

bool unionSet(int x, int y) // x와 y를 합친다. 만약 루트가 같다면, 합치는데 실패했단 의미로 false를 반환한다.

대신, 루트가 다르다면, 둘의 랭크를 비교하여 합친다.

랭크가 더 높은 쪽으로 집합을 종속시킨다.

같은 랭크라면, x에 y가 종속되도록 했다. x의 랭크를 1 더 높여주면 된다.

 

이제 Alice에 대한 union을, Bob에 대한 union을 만들어준다.

간선을 내림차순으로 정렬해준다. 그래야 타입 3부터 확인하여 간선수를 줄일 수 있기 때문이다.

타입3인경우, unionSet를 Alice와 Bob 둘 다 해주고,

2인경우 Bob만,

1인경우 Alice만 해주면 된다.

각각에 대해서, unionSet에 실패한다면(타입3의 경우 둘 중 하나라도), 필요없는 간선추가란 뜻이므로 삭제할 간선의 수인 ans를 1씩 누적시킨다.

 

이제 각 union에 대해서 순회한다.

Alice와 Bob 둘 중 하나라도 완전한 순회를 실패하면, -1을 반환한다.

완전한 순회가 가능한지는, 1부터 n까지 모두 같은 루트인지만 소속성을 확인하면 된다.

둘 다 완전한 순회가 성공하면, ans를 반환하면 된다.

 

코드

C++

class UF {
private:
    vector<int> parent;
    vector<int> rank;

public:
    UF(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for(int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if(x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    bool unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if(rootX != rootY) {
            if(rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if(rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            return true;
        }
        return false;
    }
};

class Solution {
public:
    bool isTraversable(UF& uf, int n) {
        int root = uf.find(1);
        for(int i = 2; i <= n; i++) {
            if(uf.find(i) != root) {
                return false;
            }
        }
        return true;
    }

    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
        int ans = 0;
        // union_find.
        UF union_Alice(n + 1);
        UF union_Bob(n + 1);

        sort(edges.begin(), edges.end(), [](const auto &a, const auto &b) {
            return a[0] > b[0];
        });

        for(const auto &edge : edges) {
            int type = edge[0];
            int u = edge[1];
            int v = edge[2];
            if(type == 3) {
                if(union_Alice.unionSet(u, v) | union_Bob.unionSet(u, v)) {
                } else {
                    ans++;
                }
            } else if(type == 2) {
                if(!union_Bob.unionSet(u, v)) {
                    ans++;
                }
            } else if(type == 1) {
                if(!union_Alice.unionSet(u, v)) {
                    ans++;
                }
            }
        }

        if(!isTraversable(union_Alice, n) || !isTraversable(union_Bob, n)) {
            return -1;
        }

        return ans;
    }
};