Cod sursa(job #1185150)

Utilizator andreeaghetuUNIBUC andreeaghetu andreeaghetu Data 15 mai 2014 01:24:17
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <vector>
#define pb push_back
#define p push
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");

int N, M;

struct nod
{
    int index, lowlink;
    vector <int> next;
};

int index=1;
nod v[100001];
bool st[100001];
stack <int> S;
int nr_tot=0;
vector <int> rasp[100001];

void s_c (int i)
{
    v[i].index=index;
    v[i].lowlink=index;
    ++index;
    S.p(i);
    st[i]=1;

    for (vector <int>::iterator it=v[i].next.begin(); it!=v[i].next.end(); ++it)
    {
        if (v[*it].index==0)
        {
            s_c(*it);
            v[i].lowlink=min(v[i].lowlink, v[*it].lowlink);
        }
        else
        {
            if (st[*it]==1)
                v[i].lowlink=min(v[i].lowlink, v[*it].index);
        }

    }

    if (v[i].lowlink == v[i].index)
    {

        while (S.top()!=i)
        {
            rasp[nr_tot].pb(S.top());
            st[S.top()]=0;
            S.pop();


        }

        rasp[nr_tot].pb(i);
        st[S.top()]=0;
        S.pop();

        ++nr_tot;

    }

    return;

}

int main()
{

    in>>N>>M;

    for (int i=1;i<=N;++i)
    {
        v[i].index=0;
    }

    for (int i=0;i<M;++i)
    {
        int x, y;
        in>>x>>y;
        v[x].next.pb(y);
    }

    for (int i=1;i<=N;++i)
    {
        if (v[i].index==0)
           s_c(i);
    }

    out<<nr_tot<<'\n';
    for (int i=0;i<nr_tot;++i)
    {
        for ( vector <int>::iterator it=rasp[i].begin();it!=rasp[i].end();++it)
            out<<*it<<" ";
        out<<'\n';
    }

    return 0;
}