Cod sursa(job #2677220)

Utilizator mihnea03Ciocioiu Mihnea mihnea03 Data 26 noiembrie 2020 02:06:47
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <vector>
#include <stack>
#define dim 100010
using namespace std;
vector<int> a[dim];
vector<int> sol[dim];
stack<int> s;
int f[dim];
int niv[dim];
int low[dim];
int is[dim];
int i,n,m,u,g,x,y;

void dfs (int nod) {
    g++;
    niv[nod]=g;
    low[nod]=g;
    f[nod]=1;
    is[nod]=1;
    s.push(nod);///stiva in care punem nodurile parcurse deja
    is[nod]=1;///nodul se afla in stiva
    for (auto vecin:a[nod]) {
        if (f[vecin]==0) {
            dfs(vecin);
            low[nod]=min(low[nod],low[vecin]);
        }
        else if (is[vecin]){
            low[nod]=min(low[nod],low[vecin]);
        }
    }
    ///noddurile ce se afla in acceasi componenta conexa ar trebui sa aiba acelasi low
    if (low[nod]==niv[nod]) {
        u++;
        while (s.top()!=nod) {
            sol[u].push_back(s.top());
            s.pop();
        }
        sol[u].push_back(s.top());
        s.pop();
    }
}

int main() {
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y;
        a[x].push_back(y);
    }
    for (i=1;i<=n;i++) {
        if (f[i]==0) {
            dfs(i);
        }
    }
    fout<<u<<"\n";
    for (i=1;i<=u;i++) {
        for (auto nod:sol[i]) {
            fout<<nod<<" ";
        }
        fout<<"\n";
    }
    return 0;
}