[C++] Clean Code - DFS|UnionFind


  • 8

    DFS

    class Solution {
    public:
        int findCircleNum(vector<vector<int>>& M) {
            if (M.empty()) return 0;
            int n = M.size();
            vector<bool> visited(n, false);
            int groups = 0;
            for (int i = 0; i < visited.size(); i++) {
                groups += dfs(i, M, visited) > 0;
            }
            return groups;
        }
    
    private:
        int dfs(int i, vector<vector<int>>& M, vector<bool>& visited) {
            if (visited[i]) {
                return 0;
            }
    
            int ppl = 1;
            visited[i] = true;
            for (int j = 0; j < visited.size(); j++) {
                if (i != j && M[i][j]) {
                    ppl += dfs(j, M, visited);
                }
            }
    
            return ppl;
        }
    };
    

    Could be shorter. If the dfs() doesn't care how many people in each group;

    class Solution {
    public:
        int findCircleNum(vector<vector<int>>& M) {
            if (M.empty()) return 0;
            int n = M.size();
            vector<bool> visited(n, false);
            int groups = 0;
            for (int i = 0; i < visited.size(); i++) {
                groups += !visited[i] ? dfs(i, M, visited), 1 : 0;
            }
            return groups;
        }
    
    private:
        void dfs(int i, vector<vector<int>>& M, vector<bool>& visited) {
            visited[i] = true;
            for (int j = 0; j < visited.size(); j++) {
                if (i != j && M[i][j] && !visited[j]) {
                    dfs(j, M, visited);
                }
            }
        }
    };
    

    UnionFind

    class Solution {
    public:
        int findCircleNum(vector<vector<int>>& M) {
            if (M.empty()) return 0;
            int n = M.size();
    
            vector<int> leads(n, 0);
            for (int i = 0; i < n; i++) { leads[i] = i; }   // initialize leads for every kid as themselves
    
            int groups = n;
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {   // avoid recalculate M[i][j], M[j][i]
                    if (M[i][j]) {
                        int lead1 = find(i, leads);
                        int lead2 = find(j, leads);
                        if (lead1 != lead2) {       // if 2 group belongs 2 different leads, merge 2 group to 1
                            leads[lead1] = lead2;
                            groups--;
                        }
                    }
                }
            }
            return groups;
        }
    
    private:
        int find(int x, vector<int>& parents) {
            return parents[x] == x ? x : find(parents[x], parents);
        }
    };
    

  • 0

  • 0
    P

    Its giving wrong answer for following test case
    [[1,1,0],[1,1,0],[0,0,0]]


  • 0

    @priyanka said in [C++] Clean Code:

    Its giving wrong answer for following test case
    [[1,1,0],[1,1,0],[0,0,0]]

    You must see this:
    Your input [[1,1,0],[1,1,0],[0,0,0]]
    Your answer: 2
    Expected answer: 1

    It is giving the right answer which is 2. The test implementation was wrong, it shouldn't be 1.

    in this test case, student_0 and student_1 knows each other, student_2 doesn't know any other. So there is 2 group: {0, 1} and {2}.

    This problem is not trying to find number of islands in the matrix.


  • 0
    A

    @alexander isn't this problem finding islands in a matrix?i'm confused since isn't 2 the number of islands in this test case matrix?


  • 2
    A

    @priyanka The input [[1,1,0],[1,1,0],[0,0,0]] is not valid. The description of the problem says M[i][i] = 1 for all students. The [0,0,0] have to be [0,0,1].


  • 0
    T

    whats the purpose of visited array ?. It keeps track which rows we have visited till now or which columns for a particular row ? i believe rows but wanted to confirm


  • 0
    S

    @alexander i think it is similar to isolated island problem


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.