Grouping

• 利用father id判定group

805t. Maximum Association Set

Amazon sells books, every book has books which are strongly associated with it. Given ListA and ListB,indicates that ListA [i] is associated with ListB [i] which represents the book and associated books. Output the largest set associated with each other(output in any sort). You can assume that there is only one of the largest set.

• A bookToID map

• A ans map

class UF{
    int[] parent;
    int[] size;

    public UF(int n){
        parent = new int[n];
        size = new int[n];

        for(int i=0; i<n; i++){
            parent[i] = i;
            size[i] = 1;
        }
    }

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

    public void union(int x, int y){
        int root_x = find(x);
        int root_y = find(y);

        if(root_x == root_y) return;

        if(size[root_x] < size[root_y]){
            parent[root_x] = root_y;
            size[root_y] += size[root_x];
        }else{
            parent[root_y] = root_x;
            size[root_x] += size[root_y];
        }
    }
}

public class Solution {
    public List<String> maximumAssociationSet(String[] ListA, String[] ListB) {
        UF uf = new UF(5000);
        Map<String, Integer> bookToID = new HashMap<>();

        int id=0;
        for(int i=0; i<ListA.length; i++){
            if(!bookToID.containsKey(ListA[i])) bookToID.put(ListA[i], id++);
            if(!bookToID.containsKey(ListB[i])) bookToID.put(ListB[i], id++);
            uf.union(bookToID.get(ListA[i]), bookToID.get(ListB[i]));
        }

        Map<Integer, List<String>> ans = new HashMap<>();
        for(Map.Entry<String, Integer> entry: bookToID.entrySet()){
            int root = uf.find(entry.getValue());
            if(!ans.containsKey(root)) ans.put(root, new ArrayList<String>());
            ans.get(root).add(entry.getKey());
        }

        int max=0;
        List<String> result = new ArrayList<>();
        for(List<String> list: ans.values()){
            if(list.size()>max){
                max = list.size();
                result = list;
            }
        }

        return result; 
    }
}

721. Accounts Merge

Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account. Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some email that is common to both accounts. Return the email in sorted order

• An emailToID map

• An emailToName map

• An ans map

• Use EmailToName to update the answer

class UF:
    def __init__(self):
        self.p = [i for i in range(10000)]
        
    def find(self, x):
        if x != self.p[x]: self.p[x] = self.find(self.p[x])
        return self.p[x]
    
    def union(self, x1, x2):
        self.p[self.find(x1)] = self.find(x2)

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        uf = UF()
        email_to_id = {}
        email_to_name = {}
        i = 0
        
        for acc in accounts:
            name = acc[0]
            for email in acc[1:]:
                email_to_name[email] = name
                if email not in email_to_id:
                    email_to_id[email] = i
                    i+=1
                uf.union(email_to_id[acc[1]], email_to_id[email])
        
        ans = collections.defaultdict(list)
        
        for email, id in email_to_id.items():
            ans[uf.find(id)].append(email)
            
        return [[email_to_name[li[0]]] + sorted(li) for li in ans.values()]

684. Redundant Connection

Undirect graph, use union- find

class UF:
    def __init__(self):
        self.p = [i for i in range(1001)]
        
    def find(self, x):
        if x != self.p[x]: self.p[x] = self.find(self.p[x])
        return self.p[x]
    
    def union(self, x1, x2):
        self.p[self.find(x1)] = self.find(x2)

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        uf = UF()
        
        ans = None
        for e in edges:
            if uf.find(e[0]) == uf.find(e[1]):
                ans = e
            uf.union(e[0], e[1])      
        return ans

685. Redundant Connection II

Direct Graph

"""
根據parent做出判斷
    1. p_a != p_b
        if p_b != e[1]: node的parent不是自己，已經有其他parent -> multiple parents
            不做union, 先保留答案
        else: union a and b
    2. p_a == p_b: cycle

    如果兩個條件都符合，代表第一個parent先出現了，並且造成cycle所以有兩個candidate
    找到e[1]的第一個parent
    
    Example:[[2,1],[3,1],[4,2],[1,4]]
"""

class UF:
    def __init__(self):
        self.p = [i for i in range(1001)]
        
    def find(self, x):
        if x != self.p[x]: self.p[x] = self.find(self.p[x])
        return self.p[x]
    
    # 注意有方向關係，x2的parent要指向x1
    def union(self, x1, x2):
        self.p[self.find(x2)] = self.find(x1)

class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        uf = UF()
        cand1 = None
        cand2 = None
        
        for e in edges:
            if uf.find(e[0]) != uf.find(e[1]):
                if uf.find(e[1]) != e[1]:
                    cand1 = e
                else:
                    uf.union(e[0], e[1])
            else:
                cand2 = e  
        if not cand2: return cand1
        if not cand1: return cand2
        
        for e in edges:
            if e[1] == cand1[1]:
                return e    
        return []

1202. Smallest String With Swap

Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"

"""
[0, 1], [1, 2] -> [0, 1, 2] 代表這中間的c皆可互換
sort the character array, 並依序把ch指派到idx上
"""
class UF:
    def __init__(self, n):
        self.p = list(range(n))
        
    def find(self, x):
        if x != self.p[x]: self.p[x] = self.find(self.p[x])
        return self.p[x]
    
    def union(self, x, y):
        self.p[self.find(x)] = self.find(y)

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        n = len(s)
        uf = UF(n)
        group = defaultdict(list)
        # union index
        for p in pairs:
            uf.union(p[0], p[1])
        
        # record the characters in the same group
        for idx in range(n):
            group[uf.find(idx)].append(s[idx])
        
        # sort the characters
        for v in group.values():
            v.sort()
            
        build = []
        # put the character but sequence
        for idx in range(n):
            build.append(group[uf.find(idx)].pop(0))
            
        return ''.join(build)

924. Minimize Malware Spread

In a network of nodes, each node i is directly connected to another node j if and only if graph[i][j] = 1. Some nodes initial are initially infected by malware. We will remove one node from the initial list. Return the node that if removed, would minimize the affected nodes

• Need to know size of the each init group

• If there are 2 inits in group, then it will eventually effected no matter remove any of the node

• Update when 1. group size is bigger 2. Same size but with smaller index

class DSU:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.size = [1] * n
        
    def find(self, x):
        if x != self.p[x]: self.p[x] = self.find(self.p[x])
        return self.p[x]
    
    def union(self, x, y):
        xp, yp = self.find(x), self.find(y)
        if xp == yp: return 
        self.p[xp] = yp
        self.size[yp] += self.size[xp]
        
    def getSize(self, x):
        return self.size[self.find(x)]
    
class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n = len(graph)
        dsu = DSU(n)
        
        # union connected nodes
        for i in range(n):
            for j in range(i):
                if graph[i][j] == 1:
                    dsu.union(i, j)
                    
        # check if init in same set
        uniqueCount = collections.defaultdict(int)
        for init in initial:
            uniqueCount[dsu.find(init)] += 1
    
        ans = -1
        for init in initial:
            if uniqueCount[dsu.find(init)] == 1: # the union only has 1 init
                if ans == -1:
                    ans = init
                elif dsu.getSize(init) > dsu.getSize(ans):
                    ans = init
                elif dsu.getSize(init) == dsu.getSize(ans) and init < ans:
                    ans = init

        return ans if ans != -1 else min(initial)