Cod sursa(job #1881087)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 16 februarie 2017 10:12:00
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
# include <fstream>
# include <vector>
# define DIM 100002
using namespace std;
ifstream fin("plimbare.in");
ofstream fout("plimbare.out");
vector<int> Lista[DIM],nrctc[DIM];
int /*v[DIM][DIM],*/Marcat[DIM],aux[DIM],maxim[DIM],poz[DIM],low[DIM],s[DIM];
int n,i,r,u,ctc,x,y;
void atribuie(int a[],int b[]){
    for(int i=0;i<=b[0];i++)
        a[i]=b[i];
}
void tarjan(int nc){
    r++;
    poz[nc]=r;
    low[nc]=r;
    s[++u]=nc;
    Marcat[nc]=1;
    for(int i=0;i<Lista[nc].size();i++){
        int nv=Lista[nc][i];
        if(poz[nv]==0)
            tarjan(nv);
        if(Marcat[nv])
            low[nc]=min(low[nc],low[nv]);
    }
    if(poz[nc]==low[nc]){
        ctc++;
        aux[0]=0;
        while(s[u]!=nc){
            nrctc[ctc].push_back(s[u]);
            aux[++aux[0]]=s[u];
            Marcat[s[u]]=0;
            u--;
        }
        nrctc[ctc].push_back(s[u]);
        Marcat[s[u]]=0;
        u--;
        if(maxim[0]<aux[0])
            atribuie(maxim,aux);
    }
}
int main () {
    int m;
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y;
        Lista[x].push_back(y);
        //v[x][y]=1;
    }
    tarjan(1);
    fout<<ctc<<"\n";
    for(i=1;i<=ctc;i++){
        for(int j=0;j<nrctc[i].size();j++)
            fout<<nrctc[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}