Cod sursa(job #1255028)

Utilizator Corina1997Todoran Ana-Corina Corina1997 Data 4 noiembrie 2014 06:03:21
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

ifstream is("ctc.in");
ofstream os("ctc.out");

#define INF 0x3f3f3f3f

vector<vector<int>> G, sol;
vector<int> index, L, aux;
vector<bool> instack;
int n, m, x, y, ind;
stack<int> S;

void Trajan( int k );

int main()
{
    is >> n >> m;
    G.resize(n+1);
    index = vector<int>(n+1, INF);
    L = vector<int>(n+1);
    instack = vector<bool>(n+1);
    for ( int i = 1; i <= m; i++ )
    {
        is >> x >> y;
        G[x].push_back(y);
    }

    for ( int i = 1; i <= n; i++ )
        if ( index[i] == INF )
            Trajan(i);
    os << sol.size() << "\n";
	for (const auto& c : sol)
    {
		for (const auto& x : c)
			os << x << ' ';
		os << '\n';
	}

    is.close();
    os.close();
    return 0;
}

void Trajan( int k )
{
    index[k] = L[k] = ind++;
    S.push(k);
    instack[k] = true;
    for ( const auto& y : G[k] )
        if ( index[y] == INF )
        {
            Trajan(y);
            L[k] = min(L[y], L[k] );
        }
        else
            if ( instack[k] )
                L[k] = min(L[y], L[k] );
    if ( L[k] == index[k] )
    {
        aux.clear();
        int k2;
        while( true )
        {
            aux.push_back(k2 = S.top());
            S.pop();
            instack[k] = false;
            if ( k2 == k )
                break;
        }
        sol.push_back(aux);
    }
}