Cod sursa(job #3308718)

Utilizator vlad7654vladimir manescu vlad7654 Data 27 august 2025 17:09:16
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX=1e5;
vector<int> mat[NMAX+5], tmat[NMAX+5], component(NMAX+5), x, comps[NMAX+5];
vector<bool> vizitat(NMAX+5);
int component_id=0;
void dfs(int nod){
    vizitat[nod]=1;
    for(auto it:mat[nod]){
        if(vizitat[it]==0){
            dfs(it);
        }
    }
    x.push_back(nod);
}
void dfst(int nod){
    vizitat[nod]=1;
    component[nod]=component_id;
    for(auto it:tmat[nod]){
        if(vizitat[it]==0){
            dfst(it);
        }
    }
}
int main(){
    int n, m;
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x, y;
        fin>>x>>y;
        mat[x].push_back(y);
        tmat[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        if(vizitat[i]==0){
            dfs(i);
        }
    }
    vizitat.clear();
    vizitat.resize(NMAX+5, 0);
    reverse(x.begin(),x.end());
    for(auto it:x){
        if(vizitat[it]==0){
            dfst(it);
            component_id++;
        }
    }
    fout<<component_id<<'\n';
    for(int i=1;i<=n;i++){
        comps[component[i]].push_back(i);
    }
    for(auto it:comps){
        if(it.size()!=0){
            for(auto it1:it){
                fout<<it1<<' ';
            }
            fout<<'\n';
        }else{
            return 0;
        }
    }
}