Tarjan Stack wala

PHOTO EMBED

Wed Sep 06 2023 13:46:08 GMT+0000 (Coordinated Universal Time)

Saved by @psisodiyaparek #c++

#include <iostream>
#include <set>
#include <algorithm>
#include <math.h>
#include <vector>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iterator>
// #include<bits/stdc++.h>
using namespace std;
#define forn(i, a, n) for (int i = a; i < n; i++)
#define MAXN 1000000
#define MOD 1000000007
#define int long long
#define tc    \
    int t;    \
    cin >> t; \
    while (t--)
#define TC size(arr) / size(arr[0])
#define mp make_pair
#define Radhe ios::sync_with_stdio(false);
#define Krishna cin.tie(NULL);

vector<vector<int>> graph;
int tot = 0;

void findComponent(int u, vector<int> &disc, vector<int> &lowLink, stack<int> &stk, vector<bool> &stkItem)
{
    static int time = 0;
    disc[u] = lowLink[u] = ++time;
    stk.push(u);
    stkItem[u] = true;

    for (auto x : graph[u])
    {
        {
            if (disc[x] == -1)
            {
                findComponent(x, disc, lowLink, stk, stkItem);
                lowLink[u] = min(lowLink[u], lowLink[x]);
            }
            else if (stkItem[x])
                lowLink[u] = min(lowLink[u], disc[x]);
        }
    }
    int poppedItem = 0;

    if (lowLink[u] == disc[u])
    {
        int co = 0;

        while (stk.top() != u)
        {
            poppedItem = stk.top();
            co++;
            stkItem[poppedItem] = false;
            stk.pop();
        }
        poppedItem = stk.top();
        co++;
        stkItem[poppedItem] = false;
        stk.pop();

        if (co > 1)
        {
            tot += co;
        }
    }
}

void strongConComponent(vector<vector<int>> &graph)
{
    int v = graph.size();
    vector<int> disc(v, -1), lowLink(v, -1);
    vector<bool> stkItem(v, false);
    stack<int> stk;

    for (int i = 0; i < v; i++)
        if (disc[i] == -1)
            findComponent(i, disc, lowLink, stk, stkItem);
}

void solve()
{

    tot = 0;
    int n;
    cin >> n;
    graph = vector<vector<int>>(n);
    forn(i, 0, n)
    {
        char x;
        cin >> x;
        if (x == '<')
        {
            graph[(i + 1) % n].push_back(i);
        }
        else if (x == '>')
        {
            graph[i].push_back((i + 1) % n);
        }
        else
        {
            graph[i].push_back((i + 1) % n);
            graph[(i + 1) % n].push_back(i);
        }
    }

    strongConComponent(graph);
    cout << tot << endl;
}
int32_t main()
{
    Radhe Krishna
        tc
    {
        solve();
    }

    return 0;
}
content_copyCOPY

https://www.topcoder.com/thrive/articles/tarjans-algorithm-for-strongly-connected-components