Cod sursa(job #1283238)

Utilizator maribMarilena Bescuca marib Data 5 decembrie 2014 13:32:00
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <stack>
#include <list>
#define DIM 200001

using namespace std;

int minim(int a, int  b)
{
    if(a<b) return a;
    else return b;
}

ifstream in ("ctc.in");
ofstream out("ctc.out");

int idx[DIM], lowlink[DIM], a, b, tconex[DIM], v[DIM];

int n, m, index, varf, vf, x, nrcon;

stack <int> st;

list <int> nod[DIM];

void tarjan(int vf)
{
    idx[vf]=(++index);
    lowlink[vf]=index;
    st.push(vf);
    for(list <int>::iterator j=nod[vf].begin(); j!=nod[vf].end(); ++j)
    {
        if(idx[*j]>0)
            lowlink[vf]=minim(lowlink[vf], lowlink[*j]);
        else if (idx[*j]==0)
            {
                tarjan(*j);
                lowlink[vf]=minim(lowlink[vf], lowlink[*j]);
            }
    }
    if(lowlink[vf]==idx[vf])
    {
        nrcon++;
        do
        {
            varf=st.top();
            st.pop();
            tconex[++x]=varf;
            idx[varf]=-1;
        }while(varf!=vf);
        v[nrcon]=vf;
    }
}

int main()
{
    in>>n>>m;
    while(m--)
    {
        in>>a>>b;
        nod[a].push_back(b);
    }
    index=0;
    for(int i=1; i<=n; ++i)
    {
        if(idx[i]==0)
            tarjan(i);
    }
    out<<nrcon<<"\n";
    nrcon=1;
    for(int i=1; i<=n; ++i)
    {
        out<<tconex[i]<<" ";
        if(v[nrcon]==tconex[i])
            {
                out<<"\n";
                nrcon++;
            }
    }
    in.close();
    out.close();
    return 0;
}