thảo luận Leetcode mỗi ngày

class Solution:
    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
        parents = [i for i in range(n)]
        count = [1] * n

        def find(parents, u):
            if parents[u] != u:
                parents[u] = find(parents, parents[u])
            return parents[u]

        def dsu(parents, count, u, v):
            p_u = find(parents, u)
            p_v = find(parents, v)
            if p_u == p_v:
                return 1
            if p_u < p_v:
                parents[p_v] = p_u
                count[p_u] += count[p_v]
                count[p_v] = 0
            else:
                parents[p_u] = p_v
                count[p_v] += count[p_u]
                count[p_u] = 0
            return 0
        
        removed_edges_count = 0
        for edge in edges:
            [t, u, v] = edge
            if t == 3:
                removed_edges_count += dsu(parents, count, u-1, v-1)
        
        parents_A = copy.deepcopy(parents)
        parents_B = copy.deepcopy(parents)
        count_A = copy.deepcopy(count)
        count_B = copy.deepcopy(count)

        for edge in edges:
            [t, u, v] = edge
            if t == 1:
                removed_edges_count += dsu(parents_A, count_A, u-1, v-1)
            elif t == 2:
                removed_edges_count += dsu(parents_B, count_B, u-1, v-1)
        
        if count_A[0] != n or count_B[0] != n:
            return -1
        
        return removed_edges_count

class EdgeComparator implements Comparator<int[]> {
    @Override
    public int compare(int[] a, int[] b) {
        if (a[0] == b[0]) {
            if (a[1] == b[1]) {
                return a[2] - b[2];
            }

            return a[1] - b[1];
        }
        return - (a[0] - b[0]);
    }
}
class Solution {
    public static int TYPE = 0;
    public static int U = 1;
    public static int V = 2;
    public static int ALICE = 1;
    public static int BOB = 2;
    public static int BOTH = 3;

    public int maxNumEdgesToRemove(int n, int[][] edges) {
        List<int[]> bobGraph = getEdgesByType(BOB, edges);
        List<int[]> aliceGraph = getEdgesByType(ALICE, edges);

        List<int[]> bobSPT = getSPTFromGraph(bobGraph, n);
        List<int[]> aliceSPT = getSPTFromGraph(aliceGraph, n);
        if (bobSPT == null || aliceSPT == null) return -1;

        Set<int[]> distincEdge = new TreeSet<>(new EdgeComparator());
        distincEdge.addAll(bobSPT);
        distincEdge.addAll(aliceSPT);
        System.out.println(distincEdge);

        return edges.length - distincEdge.size();
    }

    public List<int[]> getEdgesByType(int type, int[][] edges) {
        List<int[]> graph = new ArrayList<>();
        for (int[] edge : edges) {
            if (type == edge[TYPE] || BOTH == edge[TYPE]) {
                graph.add(edge);
            }
        }

        Collections.sort(graph, new EdgeComparator());

        return graph;
    }

    int[] parent;
    public List<int[]> getSPTFromGraph(List<int[]> edges, int n) {
        List<int[]> sptEdge = new ArrayList<>();
        parent = new int[n + 1];

        for(int i = 1 ; i <= n ; ++i) makeSet(-i);

        for (int[] edge : edges) {
            int u = Math.abs(findSet(edge[U]));
            int v = Math.abs(findSet(edge[V]));
            if(u != v) {
                parent[u] = v;
                sptEdge.add(new int[]{edge[TYPE], edge[U], edge[V]});
            }
        }

        Set<Integer> hashSet = new HashSet<>();
        for (int i = 1; i <= n; i++) {
            hashSet.add(findSet(i));
        }

        if (hashSet.size() != 1) {
            return null;
        }

        return sptEdge;
    }

    void makeSet(int u){
        u = Math.abs(u);
        parent[u] = u;
    }

    int findSet(int u){
        u = Math.abs(u);
        if(u == parent[u]) return u;
        return parent[u] = findSet(parent[u]);
    }
}

public class Solution
{
    public int MaxNumEdgesToRemove(int n, int[][] edges)
    {
        UnionFind alice = new(n);
        UnionFind bob = new(n);

        for (int i = 0; i < edges.Length; i++)
        {
            int[] edge = edges[i];
            if (edge[0] == 3)
            {
                alice.Union(edge[1], edge[2]);
                bob.Union(edge[1], edge[2]);
            }
        }
        int result = alice.redundant;
        alice.redundant = 0;
        bob.redundant = 0;

        for (int i = 0; i < edges.Length; i++)
        {
            int[] edge = edges[i];
            int type = edge[0];
            int u = edge[1];
            int v = edge[2];
            if (type == 1)
            {
                alice.Union(u, v);
            }
            if (type == 2)
            {
                bob.Union(u, v);
            }
        }

        if (alice.GetComponentCount() != 1 || bob.GetComponentCount() != 1)
        {
            return -1;
        }
        return result + alice.redundant + bob.redundant;
    }

    public class UnionFind
    {
        int[] parent;
        public int redundant = 0;
        
        public int GetComponentCount()
        {
            int componentCount = 1;
            for (int i = 1; i < parent.Length; i++)
            {
                int parent = Find(i);
                componentCount += parent == 1 ? 0 : 1;
            }

            return componentCount;
        }

        public UnionFind(int n)
        {
            parent = new int[n + 1];
            for (int i = 1; i <= n; i++)
            {
                parent[i] = i;
            }
        }

        public int Find(int a)
        {
            if (parent[a] == a)
            {
                return parent[a];
            }

            int result = Find(parent[a]);
            parent[a] = result;
            return result;
        }

        public void Union(int a, int b)
        {
            int aParent = Find(a);
            int bParent = Find(b);
            if (aParent == bParent)
            {
                redundant++;
                return;
            }
            if (aParent < bParent)
            {
                parent[bParent] = aParent;
                return;
            }

            parent[aParent] = bParent;
        }
    }
}

class Solution:
    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
        # step1: use type3 edges as much as possible to connect vertices for both Bob and Alice
        # step2: use type1, type2 to connect Alice vertices, Bob vertices respectively

        aliceUnions = UnionFind(n + 1)
        bobUnions = UnionFind(n + 1)

        usedEdges = 0
        for _, u, v in filter(lambda edge: edge[0] == 3, edges):
            if aliceUnions.find(u) != aliceUnions.find(v):
                usedEdges += 1
                aliceUnions.union(u, v)
                bobUnions.union(u, v)
        
        for edgeType, u, v in filter(lambda edge: edge[0] != 3, edges):
            targetUnions = aliceUnions if edgeType == 1 else bobUnions
            if targetUnions.find(u) != targetUnions.find(v):
                usedEdges += 1
                targetUnions.union(u, v)
        if not aliceUnions.getUnionCount() == bobUnions.getUnionCount() == 2:
            return -1
        return len(edges) - usedEdges

class UnionFind:
    def __init__(self, dataSize):
        self.par = list(range(dataSize))
        self.size = [1] * dataSize
        self.unionCount = dataSize

    def find(self, u):
        if self.par[u] != u:
            self.par[u] = self.find(self.par[u])
        return self.par[u]
    
    def getSize(self, u):
        return self.size[self.find(u)]
    
    def union(self, u, v):
        u, v = self.find(u), self.find(v)
        if u == v:
            return
        
        if self.size[u] < self.size[v]:
            u, v = v, u
        self.par[v] = u
        self.size[u] += self.size[v]
        self.unionCount -= 1
    
    def getUnionCount(self):
        return self.unionCount