Cod sursa(job #2054701)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 2 noiembrie 2017 13:46:21
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
# include <fstream>
# include <vector>
# include <stack>
# define DIM 100010
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
stack<int> s;
vector<int> Lista[DIM],ctc[DIM];
int Marcat[DIM],niv[DIM],low[DIM],n,m,sol,k,x,y,i,j;
void tarjan(int nc){
    k++;
    niv[nc]=low[nc]=k;
    s.push(nc);
    for(int i=0;i<Lista[nc].size();i++){
        int nv=Lista[nc][i];
        if(!niv[nv])
            tarjan(nv);
        if(!Marcat[nv])
            low[nc]=min(low[nc],low[nv]);
    }
    if(low[nc]==niv[nc]){
        sol++;
        while(s.top()!=nc){
            int nv=s.top();
            Marcat[nv]=1;
            ctc[sol].push_back(nv);
            s.pop();
        }
        s.pop();
        ctc[sol].push_back(nc);
        Marcat[nc]=1;
    }
}
int main () {
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y;
        Lista[x].push_back(y);
    }
    for(i=1;i<=n;i++)
        if(!niv[i])
            tarjan(i);
    fout<<sol<<"\n";
    for(i=1;i<=sol;i++){
        for(j=0;j<ctc[i].size();j++)
            fout<<ctc[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}