Cod sursa(job #3304339)

Utilizator InformaticianInDevenire1Munteanu Mihnea Gabriel InformaticianInDevenire1 Data 22 iulie 2025 18:24:23
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;

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

vector <int> gr[100005];
vector <int> rg[100005];
int visited[100005];
vector <int> topoSort;
vector <vector <int>> ctcs;

void Sort_Topologic(int nod){
    visited[nod] = 1;
    for (auto x:gr[nod]){
        if (!visited[x]){
            Sort_Topologic(x);
        }
    }
    topoSort.push_back(nod);
}

void Ctc_Machen(int nod,vector <int> &ctc){
    visited[nod] = 0;
    ctc.push_back(nod);
    for (auto x:rg[nod]){
        if (visited[x]){
            Ctc_Machen(x,ctc);
        }
    }
}

int main(){
    int n,m;
    fin >> n >> m;
    for (int i=1;i<=m;++i){
        int x,y;
        fin >> x >> y;
        gr[x].push_back(y);
        rg[y].push_back(x);
    }
    for (int i=1;i<=n;++i){
        if (!visited[i]){
            Sort_Topologic(i);
        }
    }
    reverse(topoSort.begin(),topoSort.end());
    for (auto nod:topoSort){
        if (visited[nod]){
            ctcs.push_back(vector <int>());
            Ctc_Machen(nod,ctcs.back());
        }
    }
    fout << ctcs.size() << '\n';
    for (auto x:ctcs){
        for (auto y:x){
            fout << y << ' ';
        }
        fout << '\n';
    }
    return 0;
}