Cod sursa(job #3340101)

Utilizator Matei_M9Mogirzan Matei-Valeriu Matei_M9 Data 12 februarie 2026 09:52:16
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>
#define nmax 100002

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,nrct,poz;
vector<int> g[nmax];
vector<int> gt[nmax];
vector<int> ctc[nmax];
bool viz[nmax];
int postordine[nmax];
void citire();
void afisare();
void dfs(int x);
void dfst(int x);
int main()
{
    int i;
    citire();
    for(i=1;i<=n;i++){
        if(!viz[i]){
            dfs(i);
        }
    }
    for(i=n;i>0;i--){
        if(viz[postordine[i]]){
            nrct++;
            dfst(postordine[i]);
        }
    }
    afisare();
    return 0;
}
void citire(){
    int i,m,x,y;
    fin>>n>>m;
    for(i=0;i<m;i++){
        fin>>x>>y;
        //y intra in lista de adiacenta a lui x in g
        g[x].push_back(y);
        //x intra in lista de adiacenta a lui y in gt
        gt[y].push_back(x);
    }
}
void afisare(){
    int i,j;
    fout<<nrct<<'\n';
    for(i=1;i<=nrct;i++){
        for(j=0;j<ctc[i].size();j++){
            fout<<ctc[i][j]<<' ';
        }
        fout<<'\n';
    }
}
void dfs(int x){
    int i;
    viz[x] = 1;
    //parcurg lista de adiacenta a lui x
    for(i=0;i<g[x].size();i++){
        if(viz[g[x][i]]==0){
            dfs(g[x][i]);
        }
    }
    postordine[++poz] = x;
}
void dfst(int x){
    int i;
    viz[x] = 0;
    ctc[nrct].push_back(x);
    for(i=0;i<gt[x].size();i++){
        if(viz[gt[x][i]]==1){
            dfst(gt[x][i]);
        }
    }
}