Cod sursa(job #2169928)

Utilizator RaduVFVintila Radu-Florian RaduVF Data 14 martie 2018 19:22:27
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
const int mmax = 200005, nmax = 100005;
int N,M,ssc,comp,viz2[nmax];
bool viz1[nmax];
vector <int> G[mmax],GT[mmax],sol[mmax];
stack <int> stiva;

void Citire () {
    int x,y;
    fin>>N>>M;
    for(int i = 1; i <= M; ++i) {
        fin>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x); // graf transpus
    }
}

void DFS1(int nod) {
    viz1[nod]=true;
    for(unsigned i=0; i<G[nod].size(); ++i) {
        int v=G[nod][i];
        if (!viz1[v]) DFS1(v);
    }
    stiva.push(nod);
}

void DFS2(int nod) {
    viz2[nod]=comp;
    for(unsigned i=0; i<GT[nod].size(); ++i) {
        int v=GT[nod][i];
        if (!viz2[v]) DFS2(v);
    }
}
int main()
{
    Citire();
    for (int i=1; i<=N; ++i)
        if(!viz1[i]) DFS1(i);
    while(!stiva.empty()) {
        ssc=stiva.top();
        stiva.pop();
        if(viz2[ssc]==0){
            comp++;
            DFS2(ssc);
        }
    }
    fout<<comp<<"\n";
    for(int i=1; i<=N; ++i)
        sol[viz2[i]].push_back(i);
    for(int i=1; i<=comp; ++i) {
        for(unsigned j=0; j<sol[i].size(); ++j)
            fout<<sol[i][j]<<' ';
        fout<<"\n";
    }
    return 0;
}