Cod sursa(job #2486811)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 3 noiembrie 2019 15:09:34
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <vector>
#include <stack>
#include <utility>
#define MAX 100001

using namespace std;

vector<int> graph[MAX];
vector<vector<int>> CTC;
stack<int> nodSt;
int low[MAX], id[MAX], idCounter;

void stocare(int nod)
{
    vector<int> ctcComp;

    while(nodSt.top() != nod)
    {
        ctcComp.push_back(nodSt.top());
        nodSt.pop();
    }

    ctcComp.push_back(nodSt.top());
    nodSt.pop();

    CTC.push_back(ctcComp);
}

void DFS(int nod)
{
    nodSt.push(nod);
    id[nod] = low[nod] = idCounter;
    idCounter++;

    for(auto i : graph[nod])
    {
        if(!id[i])
        {
            DFS(i);

            low[nod] = min(low[nod], low[i]);
        }
        else low[nod] = min(low[nod], id[i]);
    }

    if(low[nod] == id[nod])
    {
        stocare(nod);
    }
}
int main()
{
    int n, m, i, a, b;

    ifstream fin("ctc.in");
    ofstream fout("ctc.out");

    fin >> n >> m;

    for(i = 1; i <= m; i++)
    {
        fin >> a >> b;

        graph[a].push_back(b);
    }

    for(i = 1; i <= n; i++)
        if(!id[i])DFS(i);

    fout << CTC.size() << "\n";

    for(auto i : CTC)
    {
        for(auto j : i)
            fout << j << " ";

        fout << '\n';
    }

    fin.close();
    fout.close();

    return 0;
}