Cod sursa(job #1970778)

Utilizator borcanirobertBorcani Robert borcanirobert Data 19 aprilie 2017 16:29:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

using VI = vector<int>;
vector<VI> G;
int N, M;
vector<VI> ctc;
VI low, ind;
vector<bool> is;
int nr;
stack<int> st;

void Read();
void StronglyConnectedComponents();
void DFS( int nod );
void WriteComponents();

int main()
{
    Read();
    StronglyConnectedComponents();
    WriteComponents();

    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    int x, y;
    fin >> N >> M;
    G = vector<VI>(N + 1);
    is = vector<bool>(N + 1);
    low = ind = VI(N + 1);
    while ( M-- )
    {
        fin >> x >> y;

        G[x].push_back(y);
    }
}

void StronglyConnectedComponents()
{
    for ( int i = 1; i <= N; ++i )
        if ( !ind[i] )
            DFS(i);
}

void DFS( int nod )
{
    ind[nod] = low[nod] = ++nr;
    st.push(nod); is[nod] = true;

    for ( const int& v : G[nod] )
    {
        if ( !ind[v] )
        {
            DFS(v);
            low[nod] = min( low[nod], low[v] );
        }
        else
            if ( is[v] )
                low[nod] = min( low[nod], low[v] );
    }

    if ( ind[nod] == low[nod] )
    {
        VI c;
        int x;
        do
        {
            x = st.top(); st.pop(); is[x] = false;
            c.push_back(x);
        } while ( x != nod );

        ctc.push_back(c);
    }
}

void WriteComponents()
{
    fout << ctc.size() << '\n';
    for ( const auto& x : ctc )
    {
        for ( const int& y : x )
            fout << y << ' ';
        fout << '\n';
    }
}