Degress Of Separation

• Time : O(v + e)
• Space : O(v + e)

int bfs(vector<vector<int>>& adj, int u) {
    unordered_set<int> vis;
    vis.insert(u);
    queue<int> q;
    q.push(u);
    for(int i = 0; i < 6 and !q.empty(); i++) {
        int sz = q.size();
        while(sz--) {
            auto u = q.front(); q.pop();
            for(auto& v : adj[u]) {
                if(vis.count(v)) continue;
                vis.insert(v);
                q.push(v);
            }
        }
    }
    
    return vis.size();
}

string degreesOfSeparation(unordered_map<string, vector<string>> friendsLists,
                           string personOne, string personTwo) {
    unordered_map<string, int> idmp;
    int id = 1;
    for(auto& [u, adj] : friendsLists) {
        if(!idmp.count(u)) idmp[u] = id++;
        for(auto& v : adj) {
            if(!idmp.count(v)) idmp[v] = id++;
        }
    }
    vector<vector<int>> adj(id + 1);
    for(auto& [u, adjs] : friendsLists) {
        int uid = idmp[u];
        for(auto& v : adjs) {
            int vid = idmp[v];
            adj[uid].push_back(vid);
        }
    }
    int p1 = bfs(adj, idmp[personOne]), p2 = bfs(adj, idmp[personTwo]);
    int np1 = id - 1 - p1, np2 = id - 1 - p2;
    if(np1 == np2) return "";
    return np1 > np2 ? personTwo : personOne;
}