Cod sursa(job #2471261)

Utilizator AlexBolfaAlex Bolfa AlexBolfa Data 10 octombrie 2019 17:45:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX=1e5+4;

int n,postOrd[NMAX],l,nrctc=1;
bool used[NMAX];
vector <int> g[NMAX],gt[NMAX],ctc[NMAX];

void read();
void build(int);
void dfs(int);
void print();

int main(){
    read();
    int it;
    for(int i=1;i<=n;++i)
        if(!used[i])
            build(i);
    memset(used,0,sizeof used);
    for(int i=l;i>0;--i){
        if(!used[postOrd[i]]){
            dfs(postOrd[i]);
            ++nrctc;
        }
    }
    fout<<nrctc-1<<'\n';
    for(int j=1;j<nrctc;++j){
        for(int i=0;i<ctc[j].size();++i){
            it=ctc[j][i];
            fout<<it<<' ';
        }fout<<'\n';
    }
    return 0;
}
void dfs(int node){
    int it;
    ctc[nrctc].push_back(node);
    used[node]=1;
    for(int i=0;i<gt[node].size();++i){
        it=gt[node][i];
        if(!used[it])
            dfs(it);
    }
}
void build(int node){
    int it;
    used[node]=1;
    for(int i=0;i<g[node].size();++i){
        it=g[node][i];
        if(!used[it])
            build(it);
    }
    postOrd[++l]=node;
}
void read(){
    int m,x,y;
    fin>>n>>m;
    for(int i=0;i<m;++i){
        fin>>x>>y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
}