LeetCode:547.省份數量

問題描述：

有 n 個城市，其中一些彼此相連，另一些沒有相連。如果城市 a 與城市 b 直接相連，且城市 b 與城市 c 直接相連，那麼城市 a 與城市 c 間接相連。

省份 是一組直接或間接相連的城市，組内不含其他沒有相連的城市。

給你一個 n x n 的矩陣 isConnected ，其中 isConnected[i][j] = 1 表示第 i 個城市和第 j 個城市直接相連，而 isConnected[i][j] = 0 表示二者不直接相連。

傳回矩陣中 省份 的數量。

示例:

思路：

由于前幾天一直在看并查集。當看到這道題的時候，第一時間想到的就是使用并查集來解答，首先複習一下并查集，先将兩個有關聯的數通過一個數組連接配接起來，這個連接配接的操作就是并查集裡的兩個函數join()和find()。find可以找到x的祖先，由于是查找祖先，是以在查找的過程中可以将一些數的祖先賦為一個值。join通過調用find函數，将兩個數連接配接在一起如果兩個數祖先不相同，則将一個數的祖先變成另一個數的祖先。

代碼：

class Solution {
    int[] pre;//祖先數組

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        pre = new int[n];
        //其實的祖先都是自己，自己認自己做祖先！
        for (int i = 0; i < n; i++) {
            pre[i] = i;
        }
        //visited用來表示i好是否已經周遊過
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
            	//i和j有關聯
                if (isConnected[i][j] == 1) {
                    join(i, j);
                }
            }
        }
        int index = 0, count = 0;
        //count表示城市的數目
        while (index < n) {
        	//如果index這個城市已經通路過，則不用進行下面的操作
            if (visited[index]) {
                index++;
                continue;
            }
            for (int i = index + 1; i < n; i++) {
           		//如果i号城市沒有通路過且和index的祖先相同，則visited[i] = true;
                if (!visited[i] && find(index) == find(i)) {
                    visited[i] = true;
                }
            }
            count += 1;
            index++;
        }
        return count;
    }
	//用來連接配接連個有關聯的數
    public void join(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        //x和y的祖先不相同，讓x的祖先變為y的祖先
        if (fx != fy) {
            pre[fx] = fy;
        }
    }
	//查詢x的祖先并進行指派
    public int find(int x) {
        int father = x;
        while (father != pre[father]) {
            father = pre[father];
        }
        int i = x;
        while (pre[i] != father) {
            int j = pre[i];
            pre[i] = father;
            i = j;
        }
        return father;
    }
    //其實還有一個簡單的find方法，但是由于使用遞歸的方法，效率比較底下
    /*
    public void find(int x) {
        if (pre[x] != x) {
            pre[x] = find(pre[x]);
        }
        return pre[x];
    }
    */

}