Cod sursa(job #2957058)

Utilizator vlad_maneaManea Vlad Cristian vlad_manea Data 21 decembrie 2022 17:01:29
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

struct compcon {
    vector<int> noduri;
} c[100005];

struct nod {
    int index, low, viz;
} N[100005];

stack<int> S;

vector<int> G[100005];

int n, m, nrc, timp;

void citire() {
    fin>>n>>m;
    int x, y;
    for (int i=0; i<m; i++) {
        fin>>x>>y;
        G[x].push_back(y);
    }
}

void dfs(int k) {
    N[k].index=timp;
    N[k].low=timp;
    timp++;
    S.push(k);
    N[k].viz=1;
    for (auto i: G[k])
        if (!N[i].index) {
            dfs(i);
            N[k].low=min(N[k].low, N[i].low);
        } else if (N[i].viz) {
            N[k].low=min(N[k].low, N[i].index);
        }
    if (N[k].low==N[k].index) {
        int w;
        do {
            w=S.top();
            c[nrc].noduri.push_back(w);
            N[k].viz=0;
            S.pop();
        } while (w!=k && !S.empty());
        nrc++;
    }
}

void parcurgere() {
    for (int i=1; i<=n; i++)
        if (!N[i].index)
            dfs(i);
}

void afisare() {
    fout<<nrc<<"\n";
    for (int i=0; i<nrc; i++) {
        for (auto j: c[i].noduri)
            fout<<j<<" ";
        fout<<"\n";
    }
}

int main() {
    citire();
    parcurgere();
    afisare();
    return 0;
}