Cod sursa(job #2529549)

Utilizator radugnnGone Radu Mihnea radugnn Data 23 ianuarie 2020 17:23:42
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;
ifstream fin ("ctc.in");
ofstream fout("ctc.out");
int v[DIM],NIV[DIM],LOW[DIM];
int ctc,n,m,x,y,i,j,g;
stack <int> ST;
vector<int> L[DIM],C[DIM];
void dfs(int nod){
    g++;
    v[nod]=1;
    NIV[nod]=g;
    LOW[nod]=g;
    ST.push(nod);
    for(int i=0;i<L[nod].size();i++){
        int vecin = L[nod][i];
    if(v[vecin] && NIV[vecin])
        LOW[nod]=min(LOW[nod],NIV[vecin]);
    else if(!NIV[vecin]){
        dfs(vecin);
        LOW[nod]=min(LOW[nod],LOW[vecin]);
    }
    }
    if(NIV[nod]==LOW[nod]){
        ctc++;
        int aux;
        do{
            aux=ST.top();
            C[ctc].push_back(aux);
            ST.pop();
            v[aux]=0;
        }while(aux!=nod);
    }
}
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y;
        L[x].push_back(y);
    }
    for(i=1;i<=n;i++)
        if(!NIV[i])
            dfs(i);
    fout<<ctc<<"\n";

    for (i=1;i<=ctc;i++) {
        for (j=0;j<C[i].size();j++)
            fout<<C[i][j]<<" ";
        fout<<"\n";
    }

    return 0;
}