Cod sursa(job #3296209)

Utilizator Iustin_Mircea2010Iustin Mircea Iustin_Mircea2010 Data 12 mai 2025 10:09:05
Problema Componente tare conexe Scor 100
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 100001;
int n, m, viz[nmax], timp[nmax];
int curr_tm = 0;
vector<int> adj[nmax];
vector<int> revadj[nmax];
vector<int> comp[nmax];

void dfs(int v){
    //st = dr = 0;
    // coada[0] = v;
    viz[v] = 1;
    //int curr;
    for(int u : adj[v]){
        if(!viz[u])
            dfs(u);
    }
    curr_tm++;
    timp[curr_tm] = v;
}

void dfs2(int v, int nr){
    viz[v] = 1;
    comp[nr].push_back(v);
    for(int u : revadj[v]){
        if(!viz[u])
            dfs2(u, nr);
    }
}

int main()
{
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    fin >> n >> m;
    int a, b;
    for(int i = 1; i <= m; i++){
        fin >> a >> b;
        adj[a].push_back(b);
        revadj[b].push_back(a);
    }
    //int comp = 0;
    for(int i = 1; i <= n; i++){
        if(viz[i]) continue;
        //comp++;
        dfs(i);
    }
    int nr = 0;
    for(int i = 1; i <= n; i++) viz[i] = 0;
    for(int i = n; i >= 1; i--){
        if(viz[timp[i]]) continue;
        dfs2(timp[i], ++nr);
    }

    fout << nr << '\n';
    for(int i = 1; i <= nr; i++){
        sort(comp[i].begin(), comp[i].end());
        for(auto v : comp[i])
            fout << v << " ";
        fout << '\n';
    }

    return 0;
}