[UVa] 10510 - Cactus

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 10510 - Cactus
Source            : Spoj
Category          : Graph Theory, Strongly Connected Components
Algorithm         : Tarjan Algorithm
Verdict           : Accepted

#include <bits/stdc++.h>  
  
using namespace std;  
  
static const int maxn = 1e5 + 5;  
  
vector <int> graph[maxn];  
  
int father[maxn];  
int part_a_cycle[maxn];  
int sccno[maxn];  
int discovery[maxn], low[maxn];  
bool vis[maxn];  
int dfsTime;  
bool cactus;  
int tSCC;  
stack <int> S;  
  
inline void print_Nodes_Of_A_Cycle(int v, int u)  
{  
    while (father[u] != v)  
    {  
        part_a_cycle[u]++;  
        if (part_a_cycle[u] > 1)  
        {  
            cactus = false;  
            return;  
        }  
        u = father[u];  
    }  
}  
  
inline void tarjan(int u)  
{  
    vis[u] = 1;  
    discovery[u] = low[u] = ++dfsTime;  
    S.push(u);  
    for (int v : graph[u])  
    {  
        if (!vis[v])  
        {  
            father[v] = u;  
            tarjan(v);  
            low[u] = min(low[u], low[v]);  
        }  
        else if (vis[v])  
        {  
            low[u] = min(low[u], discovery[v]);  
            print_Nodes_Of_A_Cycle(v, u);  
            if (cactus == false) return;  
        }  
    }  
    if (discovery[u] == low[u]) // find a SCC  
    {  
        tSCC++;  
        if (tSCC > 1)  
        {  
            cactus = false;  
            return;  
        }  
        while (true)  // print the nodes of the SCC  
        {  
            int node = S.top(); S.pop();  
            sccno[node] = tSCC;  
            vis[node] = 0;  // update it 0 to not enter a cross edge  
            if (node == u) break;  
        }  
    }  
}  
  
inline void initialize()  
{  
    cactus = true;  
    dfsTime = 0;  
    tSCC = 0;  
    for (int i = 0; i < maxn; i++)  
    {  
        graph[i].clear();  
        discovery[i] = 0;  
        low[i] = 0;  
        vis[i] = 0;  
        sccno[i] = 0;  
        part_a_cycle[i] = 0;  
    }  
    while (!S.empty()) S.pop();  
}  
  
void findSCC(int tnode)  
{  
    for (int i = 0; i < tnode; i++)  
    {  
        if (!discovery[i])  
        {  
            tarjan(i);  
            if (cactus == false) return;  
        }  
    }  
}  
  
  
int main()  
{  
    int tc;  
    cin >> tc;  
    for (int tcase = 1; tcase <= tc; tcase++)  
    {  
        initialize();  
        int tnode, tedge;  
        cin >> tnode >> tedge;  
        for (int e = 0; e < tedge; e++)  
        {  
            int u, v;  
            cin >> u >> v;  
            graph[u].push_back(v);  
        }  
        findSCC(tnode);  
        if (cactus == true) cout << "YES" << endl;  
        else cout << "NO" << endl;  
    }  
}