Planets and Kingdoms

A game has n planets, connected by m teleporters. Two planets a and b belong to the same kingdom exactly when there is a route both from a to b and from b to a. Your task is to determine for each planet its kingdom.

Example:

Input:  n = 5, m = 6, edges = {{1, 2}, {2, 3}, {3, 1}, {3, 4}, {4, 5}, {5, 4}}

Output:

2
1 1 1 2 2

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

vector<long long> adj1[100005], adj2[100005];
stack<long long> st;
long long vis[100005];
void dfs(long long s)
{
    if (vis[s])
        return;
    vis[s] = 1;
    for (auto i : adj1[s])
        dfs(i);
    st.push(s);
}
long long k = 0;
void dfs2(long long s)
{
    if (vis[s])
        return;
    vis[s] = k;
    for (int i : adj2[s])
        dfs2(i);
}
vector<long long> planetsAndKingdom(long long n, long long m,
                                    vector<vector<long long>> &edges)
{

    for (long long i = 0; i < m; i++)
    {
        long long a = edges[i][0], b = edges[i][1];

        adj1[a].push_back(b);
        adj2[b].push_back(a);
    }
    for (long long i = 1; i <= n; i++)
    {

        //if not visited call for dfs
        if (!vis[i])
            dfs(i);
    }

    //fill with zeros
    memset(vis, 0, sizeof(vis));

    while (!st.empty())
    {
        long long x = st.top();
        st.pop();
        if (!vis[x])
        {
            k++;
            dfs2(x);
        }
    }

    vector<long long> res;
    res.push_back(k);

    for (long long i = 1; i <= n; i++)
        res.push_back(vis[i]);
    return res;
}
int main()
{
    long long n = 5, m = 6;

    vector<vector<long long>> edges = {{1, 2},
                                       {2, 3},
                                       {3, 1},
                                       {3, 4},
                                       {4, 5},
                                       {5, 4}};

    vector<long long> res = planetsAndKingdom(n, m, edges);

    cout << res[0] << "\n";

    for (long long i = 1; i < res.size(); i++)
        cout << res[i] << " ";

    return 0;
}