Cod sursa(job #1283294)

Utilizator blue_skyPetrica Stefan Cosmin blue_sky Data 5 decembrie 2014 15:00:19
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <list>
#include <stack>
#define DIM 100001

using namespace std;

list<int> nod[DIM],sol[DIM];
stack<int> st;
int n,m,x,y,indx[DIM],lowlink[DIM],index,nr;

void tarjan(int k)
{
    ++index;
    indx[k]=index;
    lowlink[k]=index;
    st.push(k);
    for(list<int>::iterator i=nod[k].begin();i!=nod[k].end();++i)
    {
        if(indx[*i]==0)
        {
            tarjan(*i);
            lowlink[k]=min(lowlink[k],lowlink[*i]);
        }
        else if(indx[*i]>0)
            lowlink[k]=min(lowlink[k],lowlink[*i]);
    }
    if(lowlink[k]==indx[k])
    {
        ++nr;
        int vf;
        do
        {
            vf=st.top();
            sol[nr].push_back(vf);
            indx[vf]=-1;
            st.pop();
        }while(vf!=k);
    }
}

int main()
{
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        f>>x>>y;
        nod[x].push_back(y);
    }
    for(int i=1;i<=n;++i)
    {
        if(indx[i]==0)
            tarjan(i);
    }
    g<<nr<<'\n';
    for(int i=1;i<=nr;++i)
    {
        for(list<int>::iterator j=sol[i].begin();j!=sol[i].end();++j)
            g<<*j<<" ";
        g<<'\n';
    }
    f.close();
    g.close();
    return 0;
}