Cod sursa(job #2927888)

Utilizator LuciBBadea Lucian LuciB Data 21 octombrie 2022 18:54:37
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 1e5;

vector<int> graph[NMAX + 1], rev[NMAX + 1], stackOrder, comp[NMAX];
bool viz[NMAX + 1];

void dfs(int node, vector<int>* g, vector<int>& v) {
    viz[node] = true;
    for(auto neighbour : g[node]) {
        if(viz[neighbour] == false) {
            dfs(neighbour, g, v);
        }
    }
    v.push_back(node);
}

int main() {
    int n, m, nComp;
    FILE *fin, *fout;
    fin = fopen("ctc.in", "r");
    fout = fopen("ctc.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(int i = 0; i < m; i++) {
        int a, b;
        fscanf(fin, "%d%d", &a, &b);
        graph[a].push_back(b);
        rev[b].push_back(a);
    }
    for(int node = 1; node <= n; node++) {
        if(viz[node] == false)
            dfs(node, graph, stackOrder);
    }
    for(int node = 1; node <= n; node++)
        viz[node] = false;
    nComp = 0;
    while(!stackOrder.empty()) {
        int node = stackOrder.back();
        stackOrder.pop_back();
        if(viz[node] == false) {
            dfs(node, rev, comp[nComp]);
            nComp++;
        }
    }
    fprintf(fout, "%d\n", nComp);
    for(int i = 0; i < nComp; i++) {
        for(auto node : comp[i])
            fprintf(fout, "%d ", node);
        fprintf(fout, "\n");
    }
    fclose(fin);
    fclose(fout);
    return 0;
}