Cod sursa(job #2320661)

Utilizator r00t_Roman Remus r00t_ Data 14 ianuarie 2019 23:29:00
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

vector<int>vp[100000];
vector<int>vpinv[100000];
vector<int>rez[100000];
vector<pair<int,int> >times;
bool vf[10000];
int time = 0;

void resetvf(int n){
    for(int i=0; i<=n; i++)vf[i] = 0;
}

void DFSinv(int x){
    vf[x] = 1;
    time++;
    for(int i=0; i<vpinv[x].size(); i++){
        if(vf[ vpinv[x][i] ] == 0){
            DFSinv(vpinv[x][i]);
        }
    }
    time++;
    times.push_back(make_pair(time,x));
}

void DFSnorm(int x,int sols){
    vf[x] = 1;
    //cout<<x<<' ';
    rez[sols].push_back(x);
    for(int i=0; i<vp[x].size(); i++){
        if(vf[vp[x][i]] == 0){
            DFSnorm(vp[x][i], sols);
        }
    }
}

int main(){
    int n,m,a,b;
    fin>>n>>m;
    for(int i=0; i<m; i++){
        fin>>a>>b;
        vp[a].push_back(b);
        vpinv[b].push_back(a);
    }

    for(int i=1; i<=n; i++)
        if(vf[i]==0)
            DFSinv(i);

    sort(times.begin(), times.end(), greater<pair<int,int> >());
    resetvf(n);

    int sols=0;
    for(int i=0; i<times.size(); i++){
        if(vf[times[i].second] == 0){
            DFSnorm(times[i].second, sols);
            //fout<<'\n';
            sols++;
        }
    }
    fout<<sols<<'\n';
    for(int i=0; i<sols; i++){
        for(int j=0; j<rez[i].size(); j++){
            fout<<rez[i][j]<<' ';
        }
        fout<<'\n';
    }


}