Cod sursa(job #2161855)

Utilizator marcdariaDaria Marc marcdaria Data 11 martie 2018 21:23:33
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
/// Algoritmul lui Tarjan
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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

using VI = vector<int>;
int N, M;
int idx;
vector<VI> G;
VI lvl;
VI L;
vector<bool> inStack;
vector<VI> cc; ///retine componentele tare conexe
VI c; ///retine componenta tare conexa curenta
stack<int> stk;

void ReadGraph();
void Tarjan(int x);
void SCC();
void Write();

int main()
{
    ReadGraph();
    SCC();
    Write();

    return 0;
}

void ReadGraph()
{
    fin >> N >> M;
    G = vector<VI>(N + 1);
    L = lvl = VI(N + 1);
    inStack = vector<bool>(N + 1);

    while(M--)
    {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
    }

}
void Tarjan(int x)
{
    lvl[x] = L[x] = ++idx;
    stk.push(x); inStack[x] = true;

    for(const int& y : G[x])
        if(!lvl[y])
    {
        Tarjan(y);
        L[x] = min(L[x], L[y]);
    }
        else
            if (inStack[y])
            L[x] = min(L[x], lvl[y]);

    if(L[x] == lvl[x])
    {
        c.clear();
        while(!stk.empty())
        {
            int z = stk.top();
            stk.pop();
            inStack[z] = false;
            c.push_back(z);
            if(z == x)
                break;
        }
        cc.push_back(c);
    }
}
void SCC()
{
    for(int i = 1; i <= N; ++i)
        if(lvl[i] == 0)
        Tarjan(i);
}
void Write()
{
    fout << cc.size() << '\n';
    for(auto& c : cc)
    {
        for(auto& x : c)
            fout << x << " ";
        fout << '\n';
    }
}