Cod sursa(job #3372805)

Utilizator alexandra8Bratan Alexandra alexandra8 Data 5 noiembrie 2026 00:52:03
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include<vector>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m, k=0;
vector<vector<int>>adj;
vector<vector<int>>adj2;
vector<int>viz;
vector<int>ordine;
vector<vector<int>>ctc;

void DFS(int nod){
    viz[nod]=1;
    for(int vecin : adj[nod])
    {
        if (!viz[vecin])
        {
            DFS(vecin);
        }
    }
    ordine.push_back(nod);

}
void DFS2(int nod){
    viz[nod]=1;
    ctc[k].push_back(nod);
    for(int vecin : adj2[nod])
    {
        if (!viz[vecin])
        {
            DFS2(vecin);
        }
    }

}
int main()
{

    fin>>n>>m;
    adj.resize(n+5);
    adj2.resize(n+5);
    viz.resize(n+5,0);
    ctc.resize(n + 5);
    for(int i=1; i<=m;i++)
    {

        int x,y;
        fin>>x>>y;
        adj[x].push_back(y);
        adj2[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {if(!viz[i]){
        DFS(i);
    }
    }
    viz.assign(n+5,0);
    for(int i=n-1;i>=0;i--) {
        int nod=ordine[i];
        if(viz[nod]==0){
            DFS2(nod);
            k++;
        }
    }
    fout<<k<<"\n";
    for(int i=0;i<k;i++){
        for(int nod : ctc[i])
            fout<<nod<<" ";
        fout<<endl;
    }
    return 0;
}