Cod sursa(job #1366515)

Utilizator IliescuDanAndreiIliescu Dan Andrei IliescuDanAndrei Data 1 martie 2015 10:31:40
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");

int n, m, nr, w, modul, lowlink[100001], index[100001], vf[200001], urm[200001], lst[100001];
vector <int> noduri, radacini;
stack <int> st;
bool viz[100001], removed[100001];

int minim(int x, int y)
{
    if(y<x) return y;
    return x;
}

void strongconnect(int  x)
{
    int p, y;
    viz[x]=true;
    index[x]=nr;
    lowlink[x]=nr;
    nr++;
    st.push(x);
    removed[x]=false;
    p=lst[x];

    while(p!=0)
    {
        y=vf[p];
        if(!viz[y])
        {
            strongconnect(y);
            lowlink[x]=minim(lowlink[x], lowlink[y]);
        }
        else if(!removed[y]) lowlink[x]=minim(lowlink[x], index[y]);
        p=urm[p];
    }

    if(lowlink[x]==index[x] && st.top()!=x)
    {
        w++;
        do
        {
            y=st.top();
            st.pop();
            noduri.push_back(y);
            modul++;

            removed[y]=true;
        }while(x!=y);
        radacini.push_back(modul);
    }

    nr--;
}

int main()
{
    int i, j=0, x, y;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>x>>y;

        vf[i]=y;
        urm[i]=lst[x];
        lst[x]=i;

        lowlink[i]=100001;
        index[i]=100001;
    }
    for(i=1;i<=n;i++)
    {
        if(!viz[i]) strongconnect(i);
    }

    out<<w<<"\n";
    for(i=0;i<=modul-1;i++)
    {

        out<<noduri[i]<<" ";
        if(radacini[j]==i+1)
        {
            j++;
            out<<"\n";
        }
    }
    return 0;
}