Friend Circles

Question

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

Solution

這題想了一個多小時想不出來，有想試著用 DP，或者用 ArrayList 加 HashMap 解，想了一下 DP 應該是不符合，ArrayList + HashMap 解半天也只通過一半的 test case。最後直接看解答

看完解答後，覺得這題沒那麼難，如果可以朝 DFS 去想，應該會直觀許多。整體的概念就是使用 DFS，讓一個點把所有的可能性都走完(direct and indirect)。像這種要窮舉所有點，或窮舉所有可能性，記得要想到 DFS 搜索！！

public void dfs(int[][] M, int[] visited, int i) {
        for (int j = 0; j < M.length; j++) {
            if (M[i][j] == 1 && visited[j] == 0) {
                visited[j] = 1;
                dfs(M, visited, j);
            }
        }
    }
    public int findCircleNum(int[][] M) {
        int[] visited = new int[M.length];
        int count = 0;
        for (int i = 0; i < M.length; i++) {
            if (visited[i] == 0) {
                dfs(M, visited, i);
                count++;
            }
        }
        return count;
    }