'2025/02/01'에 해당되는 글 1건

summary

• Find the edge that can be removed from a connected graph with n nodes and m edges to make it a tree.

approach

• Use a union-find data structure to keep track of connected components in the graph
• Iterate through the edges, and for each edge, check if the two nodes are in the same component
• If they are, then the edge is the redundant one
• Otherwise, union the two components.

complexity

• O(n + m log n) due to the union-find operations, where n is the number of nodes and m is the number of edges.

explain

• The solution uses a union-find data structure to keep track of connected components in the graph
• The union-find data structure is initialized with each node as its own component
• Then, for each edge, the solution checks if the two nodes are in the same component by calling the `disjoint` function
• If they are, then the edge is the redundant one, and the solution returns it
• Otherwise, the solution unions the two components by calling the `uf` function
• The `disjoint` function is used to find the root of a node, and the `uf` function is used to union two components.

Solution Code:

class Solution {
public:
    int uf[1001];
    int disjoint(int x){
        if(x == uf[x]) return x;
        return uf[x] = disjoint(uf[x]);
    }
    vector findRedundantConnection(vector>& edges) {
        for(int i = 0 ; i <= 1000; i++){
            uf[i] = i;
        }
        vector ans;
        for(int i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            if(disjoint(a) != disjoint(b)){
                uf[disjoint(a)] = disjoint(b);
            } else{
                ans.push_back(a);
                ans.push_back(b);
            }
        }
        return ans;
    }
};