Cod sursa(job #1989612)

Utilizator saba_alexSabadus Alex saba_alex Data 8 iunie 2017 10:44:49
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

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

const int MAX = 100005;
vector < int > G[MAX], GT[MAX];
bool viz[MAX];
int x, ord[MAX], n, m;
vector < int > r;
vector < vector < int > > sol;

void dfs_n(int nod){

    viz[nod] = 1;
    for(auto it: G[nod])
        if(!viz[it])
            dfs_n(it);
    x++;
    ord[x] = nod;
}

void dfs_t(int nod){

    viz[nod] = 0;
    r.push_back(nod);
    for(auto it: GT[nod])
        if(viz[it])
            dfs_t(it);
}

void ctc(){

    for(int i = 1; i <= n; ++i)
        if(!viz[i])
            dfs_n(i);

    for(int i = n; i; --i)
        if(viz[ord[i]]){
            r.clear();
            dfs_t(ord[i]);
            sol.push_back(r);
        }

    fout << sol.size() << '\n';
    for(auto it: sol){
        for(auto itt: it)
            fout << itt << ' ';
    fout << endl;
    }
}

int main()
{
    fin >> n >> m;

    for(int i = 1; i <= m; ++i){
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }

    ctc();

    return 0;
}