Bai1_FriendGraph_HCMUT

bool DFS(vector<vector<int>>& friends, int v, bool* &visited)
{
    int ret = false;
    stack<int> s;
    s.push(v);
    while(!s.empty())
    {
        v = s.top();
        s.pop();
        if (visited[v]) continue;
        visited[v] = true;
        ret = true;
        for (int i = friends[v].size() - 1; i >= 0; i--)
        {
            if (!visited[friends[v][i]])
            {
                s.push(friends[v][i]);
            }
        }
    }
    return ret;
}
int numberOfFriendGroups(vector<vector<int>>& friends) {
    // STUDENT ANSWER
    int n = friends.size();
    int count = 0;
    bool *visited = new bool[n];
    for (int i = 0; i < n; i++)
        visited[i] = false;
    for (int i = 0; i < n; i++)
    {
        if (DFS(friends, i, visited) == true) count++;
    }
    return count;
}