Cod sursa(job #3300473)

Utilizator ValiAntonieAntonie Valentin ValiAntonie Data 16 iunie 2025 13:21:00
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

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


int n,m,a,b, mark[50005], mark2[50005],nr;
vector <int> v[50005], w[50005];
vector <int> rasp[50005];
stack <int> S;

void DFS(int nod){
    for (int i = 0; i < v[nod].size(); i++){
        if (!mark[v[nod][i]]){
            mark[v[nod][i]] = 1;
            DFS(v[nod][i]);
        }
    }
    S.push(nod);
}


void DFS2(int nod){
    rasp[nr].push_back(nod);
    for (int i = 0; i < w[nod].size(); i++){
        if (!mark2[w[nod][i]]){
            mark2[w[nod][i]] = 1;
            DFS2(w[nod][i]);
        }
    }
}


int main()
{
fin>>n>>m;
for (int i = 1; i <= m; i++){
    fin>>a>>b;
    v[a].push_back(b);
    w[b].push_back(a);
}
for (int j = 1; j <= n; j++){
    if(!mark[j]){
        mark[j] = 1;
        DFS(j);
    }
}

while(!S.empty()){
    int j = S.top();
    if(!mark2[j]){
        mark2[j] = 1;
        nr++;
        DFS2(j);
    }
    S.pop();
}
fout << nr << '\n';
for (int i = 1; i <= nr; i++){
    for (int j = 0; j < rasp[i].size(); j++){
        fout << rasp[i][j] << " ";
    }
    fout << '\n';
}
    return 0;
}