Cod sursa(job #928397)

Utilizator SteveStefan Eniceicu Steve Data 26 martie 2013 13:55:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

int N, M, cnt = -1;
vector <int> muchii[100011];
vector <int> transp[100011];
vector <int> noduri;
vector <int> Ans[100011];

void Citire ()
{
    ifstream fin ("ctc.in");
    fin >> N >> M;
    for (int i = 0, a, b; i < M; i++)
    {
        fin >> a >> b;
        muchii[a].push_back (b);
        transp[b].push_back (a);
    }
    fin.close ();
}

int viz[100011];

void DFS1 (int nod)
{
    viz[nod] = 1;
    for (int i = 0; i < muchii[nod].size (); i++)
    {
        if (!viz[muchii[nod][i]])
            DFS1 (muchii[nod][i]);
    }
    noduri.push_back (nod);
}

void Scriere ()
{
    ofstream fout ("ctc.out");
    fout << cnt + 1 << "\n";
    for (int i = 0; i <= cnt; i++)
    {
        for (int j = 0; j < Ans[i].size (); j++)
            fout << Ans[i][j] << " ";
        fout << "\n";
    }
    fout.close ();
}

void DFS2 (int nod)
{
    viz[nod] = 1;
    Ans[cnt].push_back (nod);
    for (int i = 0; i < transp[nod].size (); i++)
        if (!viz[transp[nod][i]]) DFS2 (transp[nod][i]);
}

int main ()
{
    Citire ();
    for (int i = 1; i <= N; i++)
        if (!viz[i]) DFS1 (i);
    memset (viz, 0, sizeof (viz));
    for (; !noduri.empty (); noduri.pop_back ())
        if (!viz[noduri.back ()])
        {
            ++cnt;
            DFS2 (noduri.back ());
        }
    Scriere ();
    return 0;
}