Cod sursa(job #3372659)

Utilizator Vlad_prisVlad Prismareanu Vlad_pris Data 4 noiembrie 2026 17:16:04
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<vector<int>> Adj;
void read(vector<vector<int>>& Adj,int n,int m){
    int x,y;
    Adj.resize(n + 1);

    for(int i=1;i<=m;i++){
        fin>>x>>y;
        Adj[x].push_back(y);
    }
}
void dfs(int node, vector<int>& visited, vector<int>& order) {
    visited[node] = 1;
    for (int neighbor : Adj[node]) {
        if (visited[neighbor] == 0) {
            dfs(neighbor, visited, order);
        }
    }
    order.push_back(node);
}
vector<vector<int>> reverse(const vector<vector<int>>& Adj){
    vector<vector<int>> reversed(Adj.size());
    for (int i = 1; i < Adj.size(); ++i) {
        for (int neighbor : Adj[i]) {
            reversed[neighbor].push_back(i);
        }
    }
    return reversed;
}
void dfs_component(int node, vector<int>& visited, vector<int>& component, const vector<vector<int>>& reversed) {
    visited[node] = 1;
    component.push_back(node);
    for(int neighbor : reversed[node]){
        if(!visited[neighbor]){
            dfs_component(neighbor, visited, component, reversed);
        }
    }
}
int main(){
    int n, m;
    fin >> n >> m;
    read(Adj, n, m);
    vector<int> visited(n + 1, 0);
    vector<int> order;
    for(int i= 1; i <= n ;i++){
        if(!visited[i]){
            dfs(i,visited,order);
        }
    }
    vector<vector<int>> reversed = reverse(Adj);
    visited.assign(n + 1, 0);
    vector<vector<int>> components;
    for(int i = order.size() -1 ; i>=0;i--){
        int node = order[i];
        if(!visited[node]){
            vector<int> component;
            dfs_component(node, visited, component, reversed);
            components.push_back(component);
        }
    }
    fout << components.size() << "\n";
    for(const auto& component : components){
        for(int node : component){
            fout << node << " ";
        }
        fout << "\n";
    }
    return 0;
}