Cod sursa(job #3374776)

Utilizator TLuca2021Teodorescu Luca Nicolae TLuca2021 Data 9 noiembrie 2026 11:37:35
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void dfs1(int node, vector<int> &numbers, vector<vector<int>> &adj, vector<bool> &visited){
    visited[node] = true;
    for(auto it : adj[node]){
        if(!visited[it]){
            dfs1(it, numbers, adj, visited);
        }
    }
    numbers.push_back(node);
}
void dfs2(int node, int counter, vector<vector<int>> &new_adj, vector<bool> &visited, vector<vector<int>> &components){
    visited[node] = true;
    for(auto it : new_adj[node]){
        if(!visited[it]){
            //trebuie puse in aceeasi componenta conexa
            components[counter].push_back(it);
            dfs2(it, counter, new_adj, visited, components);
        }
    }
}
int main(){
    int n, m;
    fin >> n >> m;
    vector<vector<int>> adj(n, vector<int>());
    vector<int> numbers;
    vector<bool> visited(n, false);
    vector<vector<int>> components;
    for(int i = 0; i < m; i++){
        int first_node, second_node;
        fin >> first_node >> second_node;
        first_node--;
        second_node--;
        adj[first_node].push_back(second_node);
    }
    for(int i = 0; i < n; i++){
        if(!visited[i]) {
            dfs1(i, numbers, adj, visited);
        }
    }
    for(int i = 0; i < n; i++){
        visited[i] = false;
    }
    vector<vector<int>> new_adj(n, vector<int>());
    for(int i = 0; i < n; i++){
        for(auto it : adj[i]){
            new_adj[it].push_back(i);
        }
    }
    int n_size = numbers.size(), index = n_size - 1, counter = -1;
    while(n_size){
        if(!visited[numbers[index]]){
            counter++;
            components.push_back({});
            components[counter].push_back(numbers[index]);
            dfs2(numbers[index], counter, new_adj, visited, components);
        }
        n_size--;
        index--;
    }
    fout << counter + 1 << '\n';
    for(int i = 0; i < components.size(); i++){
        for(auto it : components[i]){
            fout << it + 1 << " ";
        }
        fout << '\n';
    }
    return 0;
}