Cod sursa(job #3344917)

Utilizator TeodoRazvanStancu Teodor-Razvan TeodoRazvan Data 6 martie 2026 17:34:04
Problema Componente tare conexe Scor 100
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;
vector<vector<int>>a,t,ctc;
vector<int>ts;
vector<bool>viz;
void topsort(int nod) {
    viz[nod]=true;
    for (auto f:a[nod]) {
        if (!viz[f]) topsort(f);
    }
    ts.push_back(nod);
}

void kosaraju(int nod,vector<int>&cc) {
    cc.push_back(nod);
    viz[nod]=true;
    for (auto f:t[nod]) {
        if (!viz[f]){
            kosaraju(f,cc);
        }
    }
}

int main() {
    fin>>n>>m;
    a.resize(n+1);
    t.resize(n+1);
    viz.resize(n+1);
    int x,y;
    for (int i=1;i<=m;i++) {
        fin>>x>>y;
        a[x].push_back(y);
        t[y].push_back(x);
    }
    for (int i=1;i<=n;i++) {
        if (!viz[i]) {
            topsort(i);
        }
    }
    fill(viz.begin(),viz.end(),false);
    reverse(ts.begin(),ts.end());
    for (int i=0;i<n;i++) {
        if (!viz[ts[i]]) {
            vector<int>cur;
            kosaraju(ts[i],cur);
            ctc.push_back(cur);
        }
    }
    fout<<ctc.size()<<'\n';
    for (auto x:ctc) {
        for (auto y:x) fout<<y<<" ";
        fout<<'\n';
    }
    return 0;
}