Cod sursa(job #2174520)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 16 martie 2018 12:25:04
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
# include <fstream>
# include <algorithm>
# 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],poz[DIM],low[DIM],n,m,x,y,i,j,niv,nrctc;
void tarjan(int nc){
    niv++;
    poz[nc]=low[nc]=niv;
    s.push(nc);
    for(int i=0;i<Lista[nc].size();i++){
        int nv=Lista[nc][i];
        if(!poz[nv])
            tarjan(nv);
        if(!Marcat[nv])
            low[nc]=min(low[nv],low[nc]);
    }
    if(low[nc]==poz[nc]){
        nrctc++;
        while(s.top()!=nc){
            ctc[nrctc].push_back(s.top());
            Marcat[s.top()]=1;
            s.pop();
        }
        ctc[nrctc].push_back(s.top());
        Marcat[s.top()]=1;
        s.pop();
    }
}
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(!poz[i])
            tarjan(i);
    fout<<nrctc<<"\n";
    for(i=1;i<=nrctc;i++){
        sort(ctc[i].begin(),ctc[i].end());
        for(j=0;j<ctc[i].size();j++)
            fout<<ctc[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}