package leetcode;

/**
 * https://leetcode.com/problems/friend-circles/
 */
public class Problem547 {
    public int findCircleNum(int[][] M) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem547 prob = new Problem547();

        System.out.println(prob.findCircleNum(new int[][]{
            {1, 1, 0},
            {1, 1, 0},
            {0, 0, 1}
        })); // 2

        System.out.println(prob.findCircleNum(new int[][]{
            {1, 1, 0},
            {1, 1, 1},
            {0, 1, 1}
        })); // 1
    }
}

@@ -12,16 +12,91 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.HashSet;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -224,358 +224,904 @@
     
-// TODO%0A        return 0;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem547 prob = new Problem547();%0A%0A        System.out.println(prob.findCircleNum(new int%5B%5D%5B%5D%7B%0A            %7B1, 1, 0%7D,%0A            %7B1, 1, 0%7D,%0A            %7B0, 0, 1%7D%0A        %7D)); // 2%0A%0A        System.out.println(prob.findCircleNum(new int%5B%5D%5B%5D%7B%0A            %7B1, 1, 0%7D,
+UnionFind uf = new UnionFind();%0A        for (int i = 0; i %3C M.length; i++) %7B%0A            for (int j = 0; j %3C M%5Bi%5D.length; j++) %7B%0A                if (M%5Bi%5D%5Bj%5D == 1) %7B%0A                    uf.union(i, j);%0A                %7D%0A            %7D%0A        %7D%0A        return new HashSet%3C%3E(uf.map.values()).size();%0A    %7D%0A%0A    private static class UnionFind %7B%0A        private final Map%3CInteger, Integer%3E map = new HashMap%3C%3E();%0A%0A        public void union(int a, int b) %7B%0A            if (!map.containsKey(a)) %7B%0A                map.put(a, a);%0A            %7D%0A            if (!map.containsKey(b)) %7B%0A                map.put(b, b);%0A            %7D%0A            if (map.get(a) == map.get(b)) %7B%0A                return; // already connected%0A            %7D%0A            for (Map.Entry%3CInteger, Integer%3E e : map.entrySet()) %7B%0A                if (e.getValue().equals(map.get(a))) %7B%0A                    map.put(e.getKey(), map.get(b));
 %0A   
@@ -1133,18 +1133,13 @@
     
-%7B1, 1, 1%7D,
+    %7D
 %0A   
@@ -1151,16 +1151,8 @@
     
-%7B0, 1, 1
 %7D%0A  
@@ -1162,16 +1162,8 @@
    %7D
-)); // 1
 %0A   

Solve problem 547