Cod sursa(job #2666892)

Utilizator Alinnus1Anghel Alin Alinnus1 Data 2 noiembrie 2020 16:20:56
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("ctc.in");
ofstream g("ctc.out");

int N,M;
const int NMAX = 100005;

#define Min(a, b)  ((a) < (b) ? (a) : (b))

vector <int> adj[NMAX], con, idx, lowlink, in_stack;

vector < vector <int> > Solution;

stack <int> S;

int indecs;

void read(vector <int>* adj )
{
    int  x, y;
    f>>N>>M;
    for(int i=0;i<M;i++)
        f >> x >> y,
        adj[x - 1].push_back(y - 1);

}

void print(const vector < vector <int> >& G)
{
    g << G.size() << "\n";
    for (int i = 0; i < G.size(); ++ i)
    {
        for (int j = 0; j < G[i].size(); ++ j)
            g << G[i][j] + 1 << " ";
        g << "\n";
    }

}

void tarjan(const int n, const vector <int>* adj)
{
    idx[n] = lowlink[n] = indecs;
    indecs ++;
    S.push(n);
    in_stack[n] = 1;

    vector <int>::const_iterator it;
    for (it = adj[n].begin(); it != adj[n].end(); ++ it)
    {
        if (idx[*it] == -1) // nu a fost vizitat?
        {
            tarjan(*it, adj);
            lowlink[n] = Min(lowlink[n], lowlink[*it]);
        }
        else if (in_stack[*it])
            lowlink[n] = Min(lowlink[n], lowlink[*it]); // actualizez nivelul radacinii
    }
    if (idx[n] == lowlink[n])
    {
        con.clear();
        int node;
        do {
            con.push_back(node = S.top());
            S.pop();
            in_stack[node] = 0;
        }
        while (node != n);
        Solution.push_back(con);
    }
}

int main(void)
{
    read(adj);
    idx.resize(N), lowlink.resize(N), in_stack.resize(N);
    idx.assign(N, -1), in_stack.assign(N, 0);

    for (int i = 0; i < N; ++ i)
        if (idx[i] == -1)
            tarjan(i, adj);

    print(Solution);

    return 0;
}