Cod sursa(job #2928230)

Utilizator vlad_dimuVlad Dimulescu vlad_dimu Data 22 octombrie 2022 15:05:46
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <string.h>
#include <vector>
#define MAXN 100000
using namespace std;

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

vector<int> graph[MAXN];
vector<int> revGraph[MAXN];

bool marked[MAXN];
vector<int> stackOrder;

vector<int> components[MAXN];
int noComponents;

void addEdge(int x, int y) {
    graph[x].push_back(y);
    revGraph[y].push_back(x);
}

void resetMarked() {
    memset(marked, false, sizeof(marked));
}

void dfs(vector<int>* graph, vector<int>& visited, int node) {
    int neighbour;
    marked[node] = true;

    for (int i = 0; i < graph[node].size(); i++ ){
        neighbour = graph[node][i];
        if (!marked[neighbour])
            dfs(graph, visited, neighbour);
    }

    visited.push_back(node);
}

int main() {
    int n, m, i, x, y, j;

    fin >> n >> m;
    for( i = 1; i <= m; i++ ){
      fin >> x >> y;
      addEdge( x - 1, y - 1 );
    }

    for (x = 0; x < n; x++)
        if (!marked[x])
            dfs(graph, stackOrder, x);

    resetMarked();

    noComponents = 0;
    while (stackOrder.size()) {
        x = stackOrder.back();
        stackOrder.pop_back();

        if (!marked[x]) {
            dfs(revGraph, components[noComponents], x);
            ++noComponents;
        }
    }

    fout << noComponents << '\n';
    for( i = 0; i < noComponents; i++ ){
      for( j = 0; j < components[i].size(); j++ )
        fout << components[i][j] + 1 << ' ';
      fout << '\n';
    }
    return 0;
}