Cod sursa(job #3374297)

Utilizator ericneaguEric Neagu ericneagu Data 8 noiembrie 2026 22:13:46
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

vector<int> graf[100003];
vector<int> gtr[100003];
bool viz[100005];
vector<int> ordine;
vector<vector<int>> comps;

void dfs1(int v) {
    viz[v] = 1;
    for(int u: graf[v]) 
        if(viz[u] == 0) 
            dfs1(u);
    ordine.push_back(v);    
}

void dfs2(int v, vector<int> &comp) {
    viz[v] = 1;
    comp.push_back(v);
    for(int u: gtr[v]) 
        if(viz[u] ==0) 
            dfs2(u,comp);
}

int main() {
    int n,m;
    f>>n>>m;
    for(int i=0;i<m;i++) {
        int x,y;
        f>>x>>y;
        graf[x].push_back(y);
        gtr[y].push_back(x);
    }

    for(int i=1;i<=n;i++)
        if(viz[i]==0) {
            dfs1(i);
        }

    for(int i=1;i<=n;i++) viz[i] = 0;
    for(int i=n-1;i>=0;i--) {
        int v = ordine[i];
        if(!viz[v]) {
            vector<int> comp;
            dfs2(v,comp);
            comps.push_back(comp);
        }
    }

    g<<comps.size()<<'\n';
    for(auto c : comps) {
        for (int x: c) {
            g<<x<<' ';
        }
        g<<'\n';
    }





    return 0;
}