Cod sursa(job #1727817)

Utilizator ValentinSavoiuFMI Savoiu Valentin-Marian ValentinSavoiu Data 11 iulie 2016 17:36:08
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>
#include <stack>
#define inf 1<<30
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> G[100001];
struct desprenod
{
    int nr,pred,ok;
}car[100001];
vector <vector <int>> ctc;
vector <int> comp;
stack <int> St;
int pas,n,m,i,j,k,ok,x,y,l=0;
void tarjan (int nod)
{
    int v,i; //declara i-ul asta nenorocit local, ca altfel te ia dracu
    car[nod].nr=pas;
    car[nod].pred=pas;
    car[nod].ok=1;
    St.push(nod);
    pas++;
    for(i=0;i<G[nod].size();i++)
    {
        v=G[nod][i];
        if(car[v].nr==inf)
        {
            tarjan(v);
            car[nod].pred=min(car[nod].pred,car[v].pred);
        }
        else if(car[v].ok==1)
            car[nod].pred=min(car[nod].pred,car[v].nr);
    }
    if(car[nod].nr==car[nod].pred)
    {
        comp.clear();
        do
        {
            v=St.top();
            St.pop();
            car[v].ok=0;
            comp.push_back(v);
        }while (v!=nod) ;
        ctc.push_back(comp);
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++) car[i].nr=inf;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        G[x].push_back(y);
    }
    pas=1;
    for(i=1;i<=n;i++)
        if(car[i].nr==inf)
            tarjan(i);
    g<<ctc.size()<<'\n';
    for(i=0;i<ctc.size();i++)
    {
        for(j=0;j<ctc[i].size();j++) g<<ctc[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}