Cod sursa(job #3286547)

Utilizator uncle_sam_007ioan bulik uncle_sam_007 Data 14 martie 2025 13:00:54
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

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

const int NMAX = 100005;

vector <int> g[NMAX], gt[NMAX];
vector <int> comp[NMAX];

bool viz1[NMAX];
int viz2[NMAX];

int n;

stack <int> topo;

void dfs1(int node){
    viz1[node] = 1;
    for(auto j: g[node]){
        if(!viz1[j]){
            dfs1(j);
        }
    }
    topo.push(node);
}

int cc;

void dfs2(int node){
    viz2[node] = cc;
    comp[cc].push_back(node);
    for(auto j: gt[node]){
        if(!viz2[j]){
            dfs2(j);
        }
    }
}

void solve(){
    int m;
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
    for(int i = 1; i <= n; ++i){
        if(!viz1[i]){
            dfs1(i);
        }
    }
    while(!topo.empty()){
        int nod = topo.top();
        if(!viz2[nod]){
            cc ++;
            dfs2(nod);
        }
        topo.pop();
    }
    fout << cc << "\n";
    for(int i = 1; i <= cc; ++i){
        for(auto j:comp[i]){
            fout << j << " ";
        }
        fout << "\n";
    }
}

int main()
{
    solve();
    return 0;
}