765. Couples Holding Hands

Link

Solution

    int connectedCount = 0;
    public int minSwapsCouples(int[] row) {
        int pairNum = row.length/2;
        int[] map = new int[pairNum];
        
        for(int i = 0; i < pairNum; i++){
            map[i] = i;
        }
        
        for(int i = 0; i < pairNum; i++){
            int node1 = row[i*2];
            int node2 = row[i*2+1];
            
            int pairIndex1 = node1/2;
            int pairIndex2 = node2/2;
            union(map, pairIndex1, pairIndex2);
        }
        return connectedCount; //min = connectedCount, 
        //connectedCount are telling us how many link show be break;  
    }
    
    public void union(int[] map, int a, int b){
        int aRoot = find(map, a);
        int bRoot = find(map, b);
        
        if(aRoot != bRoot){
            map[bRoot] = aRoot;
            connectedCount++; //those two pairs has connected
        }
    }
    
    public int find(int[] map, int a){
        if(map[a] == a){
            return a;
        }
        map[a] = find(map, map[a]);
        return map[a];
    }