Cod sursa(job #2435135)

Utilizator AlexBolfaAlex Bolfa AlexBolfa Data 3 iulie 2019 11:25:06
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>
#define MAX (int)(1e5+5)
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n,ctcCount;
bool used[MAX];
vector <int> g[MAX],tg[MAX];//graph, transpoze graph
vector <int> ctc[MAX];
stack <int> stk;

void read();
void solve();
void print();
void buildstack(int);
void dfs(int);

int main(){
    read();
    solve();
    print();
    return 0;
}
void solve(){
    int i;
    for(i=1;i<=n;++i)
        if(!used[i])//daca nu a fost bagat i in stiva
            buildstack(i);

    memset(used,0,sizeof(used));

    while(!stk.empty()){//adaugam elementele din stiva in ctc
        i=stk.top();
        stk.pop();

        if(!used[i]){
            ++ctcCount;
            dfs(i);
        }
    }
}
void dfs(int x){
    ctc[ctcCount].push_back(x);
    used[x]=1;
    for(auto it: tg[x]){
        if(!used[it])
            dfs(it);
    }
}
void buildstack(int x){
    used[x]=1;

    for(auto it:g[x]){
        if(!used[it])
            buildstack(it);
    }

    stk.push(x);
}
void read(){
    int i,m,x,y;
    fin>>n>>m;
    for(i=0;i<m;++i){
        fin>>x>>y;
        g[x].push_back(y);
        tg[y].push_back(x);
    }
}
void print(){
    int i;
    fout<<ctcCount<<'\n';
    for(i=1;i<=ctcCount;++i){
        for(auto it:ctc[i])
            fout<<it<<' ';
        fout<<'\n';
    }
}