Cod sursa(job #3335865)

Utilizator ioan19Buzdugan Ioan-Michael ioan19 Data 23 ianuarie 2026 18:49:57
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

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

int E, V, v[100005], cnt;
vector<int> adj[100005], tc[100005], inv[100005];
stack<int> s;

void dfs1(int t){
    v[t] = 1;

    for(int x : adj[t])
        if(!v[x])
            dfs1(x);
    s.push(t);
}

void dfs2(int t){
    v[t] = 1;
    tc[cnt].push_back(t);

    for(int x : inv[t])
        if(!v[x])
            dfs2(x);   
}

int main(){
    f >> V >> E;
    for(int i = 1; i <= E; i++){
        int x, y;
        f >> x >> y;
        adj[x].push_back(y);
        inv[y].push_back(x);
    }

    for(int i = 1; i <= V; i++)
        if(v[i] == 0)
            dfs1(i);

    for(int i = 1; i <= V; i++)
        v[i] = 0;

    while(!s.empty()){
        int curr = s.top();
        s.pop();

        if(v[curr] == 0){
            cnt++;
            dfs2(curr);
        }
    }

    g << cnt << '\n';
    for(int i = 1; i <= cnt; i++, g << '\n'){
        sort(tc[i].begin(), tc[i].end());
        for(int x : tc[i])
            g << x << ' ';
    }

}