Leetcode - Graph

Number of Provinces

-> Here is how I solved this problem.

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int count = 0;
        boolean [] visited = new boolean[isConnected.length];
        
        for(int i = 0; i<isConnected.length;i++){
            
            if(!visited[i]) {
                find(isConnected, i, visited);
                count++;
            }
        }
     return count;   
    }
    
    private void find(int[][] isConnected, int i, boolean [] visited) {
        
        for(int j = 0; j<isConnected[i].length;j++){
            if(!visited[j] && isConnected[i][j] == 1) {
                visited[j] = true;
                find(isConnected, j, visited);
            }   
        }
    }
}

 

Here is the solution using disjoint sets.

For counting province, let's think if they share same root node, it means it is one province.

It means if you count the number of nodes which has the node itself as a root node, that is the number of province.

 

class Solution {
    // Union Find
    public int findCircleNum(int[][] isConnected) {
        if (isConnected == null || isConnected.length == 0) {
            return 0;
        }

        int n = isConnected.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }

        return uf.getCount();
    }

    class UnionFind {
        private int[] root;
        private int[] rank;
        private int count;

        UnionFind(int size) {
            root = new int[size];
            rank = new int[size];
            count = size;
            for (int i = 0; i < size; i++) {
                root[i] = i;
                rank[i] = 1;
            }
        }

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

        void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rank[rootX] > rank[rootY]) {
                    root[rootY] = rootX;
                } else if (rank[rootX] < rank[rootY]) {
                    root[rootX] = rootY;
                } else {
                    root[rootY] = rootX;
                    rank[rootX] += 1;
                }
                count--;
            }
        }

        int getCount() {
            return count;
        }
    }
}

Smallest String With Swaps (*** 다시 풀어야봐야 할 듯!!!!!)

* lexicographically : 사전식 순서대로

 

-union find 방법 활용

import java.util.*;

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int N = s.length();
        
        UnionFind uf = new UnionFind(N);
        for(List<Integer> pair : pairs) {
            uf.union(pair.get(0), pair.get(1));
        }
        
        Map<Integer, List<Character>> graphs = new HashMap<>();
        for(int i = 0; i<N;i++){
            int head = uf.find(i); //uf의 root node
            List<Character> characters = graphs.computeIfAbsent(head, (dummy) -> new ArrayList<>());
            characters.add(s.charAt(i));
        }
        
        for(List<Character> characters : graphs.values()) {
            Collections.sort(characters);
        }
    
        StringBuilder sb = new StringBuilder(N);
        for(int i = 0; i<N;i++) {
            List<Character> characters = graphs.get(uf.find(i));
            char currentMin = characters.remove(0);
            sb.append(currentMin);
        }
        return sb.toString();
        
    }
    
    private class UnionFind {
        public int [] size;
        public int [] parent;
        
        UnionFind(int count){
            size = new int[count];
            parent = new int[count];
            for(int i = 0; i<count;i++){
                size[i] = 1;
                parent[i] = i;
            }
        }
        
        int find(int p) {
            while(p !=parent[p]){
                parent[p] = parent[parent[p]];
                p = parent[p];
            }
            return p;
        }
        int union(int p, int q) {
            int pRoot = find(p);
            int qRoot = find(q);
            if(pRoot == qRoot) {
                return size[pRoot];
            }
            if(pRoot > qRoot) {
                parent[qRoot] = pRoot;
                size[pRoot] += size[qRoot];
                return size[pRoot];
            }else {
                parent[qRoot] = pRoot;
                size[qRoot] += size[pRoot];
                return size[qRoot];
            }
        }
    }
}

 

- DFS

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        char[] array = s.toCharArray();
        boolean[] visited = new boolean[s.length()];
        List<Integer>[] graph = new List[s.length()];
        for(int i = 0 ; i < array.length ; i++) {
            graph[i] = new ArrayList<>();
        }
        for(List<Integer> pair : pairs) {
            graph[pair.get(0)].add(pair.get(1));
            graph[pair.get(1)].add(pair.get(0));
        }
        for(int i = 0 ; i < array.length ; i++) {
            if(!visited[i]) {
                List<Integer> indexes = new ArrayList<>();
                List<Character> contents = new ArrayList<>();
                DFS(graph, array, indexes, contents, i, visited);
                Collections.sort(indexes);
                Collections.sort(contents);
                for(int j = 0 ; j < indexes.size() ; j++) {
                    array[indexes.get(j)] = contents.get(j);
                }
            }
        }
        return new String(array);
    }
    private void DFS(List<Integer>[] graph, char[] array, List<Integer> indexes, List<Character> contents, int start, boolean[] visited) {
        visited[start] = true;
        indexes.add(start);
        contents.add(array[start]);
        for(int child : graph[start]) {
            if(!visited[child]) {
                DFS(graph, array, indexes, contents, child, visited);
            }
        }
    }
}

 

Evaluate Division

-DFS 방법만 고민하게 된다.

1. queries[0]에 해당하는 variable을 먼저, equations의 처음부터 찾아서 찾으면queires[1]인지 확인해보고 아니면 다시 equations의 값에 나온 값을 찾아서 queries[1]과 계속 비교

2. equations[0]값에서 못 찾으면 equations[1]값을 기점으로 다시 찾아보기

3. 못 찾으면 -1