Cod sursa(job #1931987)

Utilizator TudorVersoiuVersoiu Tudor Sorin TudorVersoiu Data 19 martie 2017 15:14:46
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>

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

vector<int> G[100001], Gt[100001];

int viz[100001], post[100001];
void postordine(int x)
{
    viz[x] = 1;

    for ( vector<int>::iterator it = G[x].begin(); it!=G[x].end(); it++ )
        if ( !viz[*it] ) postordine(*it);
    post[++post[0]] = x;
}

stringstream out;

void parcurgere(int x)
{
    out << x << ' ';
    viz[x] = 0;
    for ( vector<int>::iterator it = Gt[x].begin(); it!=Gt[x].end(); it++ )
        if ( viz[*it] ) parcurgere(*it);
}

int N, M;
int main()
{
    f >> N >> M;

    for ( int i=1; i<=M; i++ )
    {
        int x, y;
        f >> x >> y;
        G [x].push_back(y);
        Gt[y].push_back(x);
    }

    for ( int i=1; i<=N; i++ )
        if ( !viz[i] ) postordine(i);

    int componente = 0;
    for ( int i=N; i>=1; i-- )
        if ( viz[post[i]] )
        {
            componente++;
            parcurgere(post[i]);
            out << '\n';
        }
    g << componente << '\n';
    g << out.str();
}