A Walk to Remember

Dilku was thinking about the first time he met his girl... It was indeed a walk to remember. The romantic weather and her silly talks. He was completely mesmerized. Those were the days!..

Today is his girl's birthday and he wants to make it special for her. He wants to again take her on a "special walk" that they would remember for a lifetime.

The city in which Dilku lives is represented as an unweighted directed graph with N nodes and M edges. A "special walk" in the graph starting at node u is a simple path that begins and ends at the same node u.

Formally, A special walk is path u , a1 , a2 , a3 ,..., ai ,.... , u where ai are distinct and not equal to u for all i.

Now since Dilku is really nervous about taking his girl out, he needs your help. For every node in the given graph, tell whether it is possible for Dilku to take his girl on a "special walk" starting at that node.

Example:

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

Approach

C++

#include <bits/stdc++.h>
using namespace std;
vector<int> arr[100001], tr[100001];
int vis[100001];
vector<int> order, SCC;
void dfs(int node)
{
    vis[node] = 1;
    for (int child : arr[node])
    {
        if (vis[child] == 0)
            dfs(child);
    }
    order.push_back(node);
}
void dfs1(int node)
{
    vis[node] = 1;
    for (int child : tr[node])
    {
        if (vis[child] == 0)
            dfs1(child);
    }
    SCC.push_back(node);
}

void walkToRemember(int n, int m, vector<vector<int>> &edges)
{
    for (int i = 0; i < m; i++)
    {
        int a = edges[i][0], b = edges[i][1];

        arr[a].push_back(b);
        tr[b].push_back(a);
    }
    for (int i = 1; i <= n; i++)
    {
        if (vis[i] == 0)
            dfs(i);
    }
    for (int i = 1; i <= n; i++)
        vis[i] = 0;
    int res[n + 1] = {0};
    for (int i = 1; i <= n; i++)
    {
        if (vis[order[n - i]] == 0)
        {
            SCC.clear();
            dfs1(order[n - i]);
            if (SCC.size() > 1)
            {
                for (int node : SCC)
                    res[node] = 1;
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << res[i] << " ";
}
int main()
{
    int n = 5, m = 5;
    vector<vector<int>> edges = {{1, 2},
                                 {2, 3},
                                 {3, 4},
                                 {4, 5},
                                 {4, 2}};

    walkToRemember(n, m, edges);

    return 0;
}