Cod sursa(job #1340976)

Utilizator Edsger.DijkstraEdsger Wybe Dijkstra Edsger.Dijkstra Data 12 februarie 2015 11:22:09
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int MAXN = 100010;

vector <int> Graf[MAXN], GrafT[MAXN];
vector < vector <int> > CTC;

int St[MAXN];
bool Viz[MAXN];

void TopSort (const int &node)
{
    Viz[node] = 1;

    vector <int> :: iterator it;
    for (it = GrafT[node].begin (); it != GrafT[node].end (); ++ it)
        if (!Viz[*it])
            TopSort (*it);

    St[++ St[0]] = node;
}

vector <int> now;

void DFS (const int &node)
{
    now.push_back (node);
    Viz[node] = 1;

    vector <int> :: iterator it;
    for (it = Graf[node].begin (); it != Graf[node].end (); ++ it)
        if (!Viz[*it])
            DFS (*it);
}

int main()
{
    int N, M, a, b;
    int i, j;

    in >> N >> M;

    for (i = 1; i <= M; i ++){
        in >> a >> b;
        Graf[a].push_back (b);
        GrafT[b].push_back (a);
    }

    for (i = 1; i <= N; i ++)
        if (!Viz[i])
            TopSort (i);

    for (i = 1; i <= N; i ++)
        Viz[i] = 0;

    for (i = N; i; i --)
        if (!Viz[St[i]]){
            now.clear ();
            DFS (St[i]);
            CTC.push_back (now);
        }
    int X = CTC.size ();

    out << X << "\n";
    for (i = 0; i < X; i ++, out << "\n")
        for (j = 0; j < CTC[i].size (); j ++)
            out << CTC[i][j] << " ";

    return 0;
}