Cod sursa(job #1917055)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 9 martie 2017 11:01:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.19 kb
#include <fstream>
#include<vector>
#include<stack>
#include<iostream>
using namespace std;
#define DIM 100000
#define N 100100
char buff[DIM];
int poz,i,n,j,m,v[N],k,index,nr_c,l;
struct data
{
    int low_link;///numarul celui mai de jos element din stiva la care se poate ajunge din nodul curent
    int index;///numarul nodului in stiva
}V[N];
bool sel_st[N];
vector<int>a[N];
stack<int>S;
vector<int>curr;
vector< vector<int> >C;///lista componentelor conexe
ifstream f("ctc.in");
inline void R(int&x)
{
    x=0;
    while(buff[poz]<'0' || buff[poz]>'9')
        if(++poz==DIM)
    {
        f.read(buff,DIM);
        poz=0;
    }
    while(buff[poz]>='0' && buff[poz]<='9')
    {
        x=x*10+buff[poz]-'0';
        if(++poz==DIM)
        {
            poz=0;
            f.read(buff,DIM);
        }
    }
}
void tare_conexa(int k)
{
    V[k].index=index;
    V[k].low_link=index;  ///la inceput fiecare nod formeaza de unul singur o componenta tare conexa
    ++index;
    S.push(k);
    sel_st[k]=1;
    int nod;
    for(int i=0;i<v[k];++i)
    {
        nod=a[k][i];
        if(!V[nod].index )
        {
            tare_conexa(nod);
            V[k].low_link=min( V[k].low_link, V[nod].low_link );
        }
        else
            if(sel_st[nod])
                V[k].low_link=min( V[k].low_link, V[nod].low_link );
    }
    if(V[k].index==V[k].low_link)///sunt la inceputul componentei conexe si golesc stiva
    {
        curr.clear();
        ++nr_c;
        nod=S.top();S.pop();
        while(k!=nod)
        {
            curr.push_back(nod);
            sel_st[nod]=0;
            nod=S.top();S.pop();
        }
        curr.push_back(nod);
        sel_st[nod]=0;
        C.push_back(curr);
    }
}
int main()
{
    R(n);R(m);
    for(l=0;l<m;++l)
    {
        R(i);R(j);
        a[i].push_back(j);
        ++v[i];
    }
    nr_c=0;index=1;
    for(i=1;i<=n;++i)
        if(!V[i].index)
            tare_conexa(i);
    ofstream g("ctc.out");
    g<<nr_c<<'\n';
    for(l=0;l<nr_c;++l)
    {
        //n=C[l].size;
        for(i=0;i<C[l].size();++i)
            g<<C[l][i]<<" ";
        g<<'\n';
    }
    return 0;
}