package question;


/*
 @author: Roderland
 @create: 2020年09月23日---15:34
*/
public class Question547 {
 public static void main(String[] args) {
 int[][] ints = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
 System.out.println(new Question547().findCircleNum(ints));
 }
 public int findCircleNum(int[][] M) {
 Union union = new Union(M.length);
 for (int i = 0; i < M.length; i++) {
 for (int j = 0; j < M[i].length; j++) {
 if (M[i][j]==1) union.merge(i, j);
 }
 }
 return union.getNum();
 }

 private static class Union {
 int[] root;

 public Union(int n) {
 root=new int[n];
 for (int i = 0; i < root.length; i++) {
 root[i]=i;
 }
 }

 public boolean merge(int x, int y) {
 x=find(x);
 y=find(y);
 if (x==y) return true;
 root[x]=y;
 return false;
 }

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

 public int getNum() {
 int cnt=0;
 for (int i = 0; i < root.length; i++) {
 if (find(i)==i) cnt++;
 }
 return cnt;
 }
 }
}