Cod sursa(job #1971503)

Utilizator patrutoiuandreipatrutoiu andrei patrutoiuandrei Data 20 aprilie 2017 14:53:46
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>

#define Ndim 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int ST[Ndim],Low[Ndim],Lev[Ndim],ctc,niv;
bool VIZ[Ndim];
vector <int> G[Ndim],SOL[Ndim];
void strongConnect(int nod)
{
    VIZ[nod] = 1;
    ++niv;
    Low[nod] = Lev[nod] = niv;
    ST[++ST[0]] = nod;
    for(vector <int> :: iterator it = G[nod].begin();it!=G[nod].end();++it)
    {
        if(!Lev[*it])
        {
            strongConnect(*it);
            Low[nod] = min(Low[nod],Low[*it]);
        }
        else if(VIZ[*it]==1)
            Low[nod] = min(Lev[nod],Low[*it]);
    }
    if(Lev[nod] == Low[nod])
    {
        ctc++;
        do
        {
            SOL[ctc].push_back(ST[ST[0]]);
            VIZ[ST[ST[0]]] = 0;
            ST[0]--;
        }while(ST[ST[0]+1]!=nod);
    }
}
int main()
{
    int n,m,i,a,b;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b;
        G[a].push_back(b);
    }
    for(i=1;i<=n;i++)
    {
        if(!Lev[i])
            strongConnect(i);
    }
    fout<<ctc<<'\n';
    for(i=1;i<=ctc;i++,fout<<'\n')
        for(vector<int> :: iterator it = SOL[i].begin();it!=SOL[i].end();++it)
            fout<<*it<<' ';
    return 0;
}