Cod sursa(job #3293158)

Utilizator laurentiu.maticaMatica Laurentiu-Andrei laurentiu.matica Data 10 aprilie 2025 14:50:36
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<int>g[100001];
vector<int>gt[100001];
vector<int>CTC[100001];
int viz[1000001],ctc;
stack<int>q;
void DFS(int nod) {
    viz[nod] = 1;
    for (auto x:g[nod])
        if(!viz[x])
            DFS(x);
    q.push(nod);
}
void DFST(int nod) {
    viz[nod] = 2;
    CTC[ctc].push_back(nod);
    for (auto x:gt[nod])
        if(viz[x]==1)
            DFST(x);
}
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i=0;i<m;i++) {
        int x,y;
        cin >> x >> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        if(!viz[i])
            DFS(i);
    while(!q.empty()) {
        int nod = q.top();
        if(viz[nod]==1) {
            ctc++;
            DFST(nod);
        }
        q.pop();
    }
    cout << ctc << endl;
    for(int i=1;i<=ctc;i++,cout << '\n')
        for(int j=0;j<CTC[i].size();j++)
            cout << CTC[i][j] << ' ';
    return 0;
}