Cod sursa(job #2766929)

Utilizator dinuionirinel10@gmail.comDinu Ion Irinel [email protected] Data 3 august 2021 21:39:45
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <vector>
#include <string>

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

std::list<int> adj[100001];
std::list<int> adj2[100001];

std::vector<std::vector<int>> result;
std::vector<int> aux;

int nr_comp = 0;

void dfs2(int source, bool *visited) {
    aux.push_back(source);
    visited[source] = true;
    for (auto &it:adj2[source]) {
        if (!visited[it]) {
            dfs2(it, visited);
        }
    }
}

void dfs(int source, bool *visited, std::stack<int>& stack) {
    visited[source] = true;
    for (auto &it: adj[source]) {
        if (!visited[it]) {
            dfs(it, visited, stack);
        }
    }
    stack.push(source);

}

int main(void) {

    // read inputs
    int n, m, nr_comp = 0;
    fin >> n >> m;

    for (int i = 1; i <= m; ++i) {
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
        // transpose graph
        adj2[y].push_back(x);
    }   

    // k algorithm
    std::stack<int> stack;
    bool visited[n];
    for (int i = 1; i <= n; ++i) {
        visited[i] = false;
    }   

    for (int i = 1; i <= n; ++i) {
        if (visited[i] == false) {
            dfs(i, visited, stack);
        }
    }

    for (int i = 1; i <= n; ++i) {
        visited[i] = false;
    }   

    while (!stack.empty()) {
        int top = stack.top();
        stack.pop();
        if (visited[top] == false) {
            aux.clear();
            nr_comp++;
            dfs2(top, visited);
            result.push_back(aux);
        }
    }
    
    fout << nr_comp << "\n";
    for (auto it:result) {
        for (auto it2:it) {
            fout << it2 << " ";
        }
        fout << "\n";
    }
    fin.close();
    fout.close();
    
    return 0;
}