Cod sursa(job #3187911)

Utilizator Robert_NicuNicu Robert Cristian Robert_Nicu Data 31 decembrie 2023 12:53:56
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
#define DIM 100001
using namespace std;

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

int n, m, a, b, ans;
bool parcurs[DIM];
int i, j;
vector <int> G[DIM], Gtrans[DIM], rez[DIM];
stack <int> st;

void dfs(int nod){
    parcurs[nod]=1;
    for(int i=0; i<G[nod].size(); i++){
        int fiu=G[nod][i];
        if(!parcurs[fiu])
            dfs(fiu);
    }
    st.push(nod);
}

void dfst(int nod){
    parcurs[nod]=0;
    rez[ans].push_back(nod);
    for(int i=0; i<Gtrans[nod].size(); i++){
        int fiu=Gtrans[nod][i];
        if(parcurs[fiu])
            dfst(fiu);
    }
}

int main(){
    fin>>n>>m;
    for(i=1; i<=m; i++){
        fin>>a>>b;
        G[a].push_back(b);
        Gtrans[b].push_back(a);
    }
    for(i=1; i<=n; i++){
        if(!parcurs[i]){
            dfs(i);
        }
    }
    while(!st.empty()){
        if(parcurs[st.top()]){
            ans++;
            dfst(st.top());
        }
        st.pop();
    }
    fout<<ans<<"\n";
    for(j=1; j<=ans; j++){
        for(i=0; i<rez[j].size(); i++){
            fout<<rez[j][i]<<" ";
        }
        fout<<"\n";
    }

}