Cod sursa(job #2273299)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 31 octombrie 2018 12:09:04
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
#include <stack>
#define DIM 100010
using namespace std;

ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector <int> L[DIM],a[DIM];
stack <int> s;
int n,m,i,j,g,c,x,y;
int nv[DIM],low[DIM],f[DIM];

int dfs (int nod){
    g++;
    nv[nod] = g;
    low[nod] = g;
    s.push (nod);
    f[nod] = 1;
    for (int i=0;i<L[nod].size();i++){
        int vecin = L[nod][i];
        if (!nv[vecin]){
            dfs (vecin);
            low[nod] = min (low[nod],low[vecin]);
        } else {
            if (f[vecin])
                low[nod] = min (low[nod],low[vecin]);
        }
    }

    if (nv[nod] == low[nod]){ /// avem o componenta tare conexa
        c++;
        int nr = nod;
        do{
            nr = s.top();
            a[c].push_back (nr);
            f[nr] = 0;
            s.pop();

        } while (nr != 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 (!nv[i])
            dfs (i);

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

    return 0;
}