Cod sursa(job #2925798)

Utilizator Teodor94Teodor Plop Teodor94 Data 16 octombrie 2022 05:11:50
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>
using namespace std;

#define NO_NODES 100000

int noNodes;
vector<int> graph[NO_NODES];
vector<int> revGraph[NO_NODES];

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

vector<int> components[NO_NODES];

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) {
    marked[node] = true;

    for (int neighbour : graph[node])
        if (!marked[neighbour])
            dfs(graph, visited, neighbour);

    visited.push_back(node);            
}

int main() {
    FILE *fin, *fout;
    fin = fopen("ctc.in", "r");
    fout = fopen("ctc.out", "w");

    int noEdges, noComponents;
    int x, y;

    fscanf(fin, "%d%d", &noNodes, &noEdges);
    while (noEdges--) {
        fscanf(fin, "%d%d", &x, &y);
        addEdge(x - 1, y - 1);
    }

    for (x = 0; x < noNodes; ++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;
        }
    }

    fprintf(fout, "%d\n", noComponents);
    for (x = 0; x < noComponents; ++x, fputc('\n', fout))
        for (int node : components[x])
            fprintf(fout, "%d ", node + 1);

    fclose(fin);
    fclose(fout);
    return 0;
}