C++ BFS Solution


  • 0
    J

    class Solution {
    public:
    int findCircleNum(vector<vector<int>>& M) {
    bool* v = new bool[M.size()];
    for (int i = 0; i < M.size(); i++) {
    v[i] = false;
    }
    int result=0;
    for (int i = 0; i < M.size(); i++) {
    if (!v[i]) {
    bfs(M, v,i);
    result++;
    }
    }
    return result;
    }
    void bfs(vector<vector<int>>& M, bool* &v,int tempdex) {
    stack<int> mystack;
    mystack.push(tempdex);
    while (mystack.size()) {
    tempdex = mystack.top();
    mystack.pop();
    v[tempdex] = true;
    for (int i = 0; i < M.size(); i++) {
    if (!v[i] && M[tempdex][i]) {
    mystack.push(i);
    v[i] = true;
    }
    }
    }
    }
    };


Log in to reply
 

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