LeetCode - Algorithms - 547. Friend Circles

Problem

547. Friend Circles

Java

union–find

© 1.5 Case Study: Union-Find Copyright © 2000–2019 Robert Sedgewick and Kevin Wayne. All rights reserved.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
    public int findCircleNum(int[][] M) {
        int N = M.length;
        UF uf = new UF(N);
        for(int i=0; i<N; i++) {
            for(int j=0; j<i; j++) {
                if (M[i][j]==1)
                    uf.union(i,j);
            }
        }
        return uf.count();        
    }
}

/**
 * Weighted quick-union by rank with path compression by halving.
 * @author Robert Sedgewick
 * @author Kevin Wayne
 * Algorithms, 4th edition textbook code and libraries
 * https://github.com/kevin-wayne/algs4
 */
class UF {
    private int[] parent;
    private byte[] rank;
    private int count;

    public UF(int n) {
        if (n < 0) throw new IllegalArgumentException();
        count = n;
        parent = new int[n];
        rank = new byte[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int p) {
        validate(p);
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    public int count() {
        return count;
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;

        if      (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ;
        else if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP;
        else {
            parent[rootQ] = rootP;
            rank[rootP]++;
        }
        count--;
    }

    private void validate(int p) {
        int n = parent.length;
        if (p < 0 || p >= n) {
            throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));
        }
    }
}

Submission Detail

  • 113 / 113 test cases passed.
  • Runtime: 1 ms, faster than 72.63% of Java online submissions for Friend Circles.
  • Memory Usage: 40.3 MB, less than 68.00% of Java online submissions for Friend Circles.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
    public int findCircleNum(int[][] M) {
        int N = M.length;
        List<Edge> edges = new ArrayList<Edge>();
        for(int i=0; i<N; i++) {
            for(int j=0; j<i; j++) {
                if (M[i][j]==1) {
                    edges.add( new Edge(i,j) );
                    edges.add( new Edge(j,i) );
                }
            }
        }
        Graph graph = new Graph(edges, N);
        boolean[] visited = new boolean[N];
        for(int i=0; i<N; i++)
            visited[i] = false;
        int c = 0;
        for(int i=0; i<N; i++) {
            if (!visited[i]) {
                dfs(graph, i, visited);
                c++;
            }
        }

        return c;        
    }
    
    private void dfs(Graph graph, int v, boolean[] visited) {
        visited[v] = true;
        for (int u : graph.adjList.get(v)) {
            if (!visited[u])
                dfs(graph, u, visited);
        }
    }
}

class Edge {
	int source, dest;

	public Edge(int source, int dest) {
		this.source = source;
		this.dest = dest;
	}
}

class Graph {
	List<List<Integer>> adjList = null;

	Graph(List<Edge> edges, int N) {
		adjList = new ArrayList<>(N);

		for (int i = 0; i < N; i++) {
			adjList.add(i, new ArrayList<>());
		}

		for (Edge edge : edges) {
			adjList.get(edge.source).add(edge.dest);
		}
	}
}

Submission Detail

  • 113 / 113 test cases passed.
  • Runtime: 4 ms, faster than 25.38% of Java online submissions for Friend Circles.
  • Memory Usage: 40.1 MB, less than 72.00% of Java online submissions for Friend Circles.

Resources