Cod sursa(job #1427990)

Utilizator RaileanuCristian Raileanu Raileanu Data 3 mai 2015 14:24:23
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <list>
using namespace std;
ifstream f1("ctc.in");
ofstream f2("ctc.out");
#define MX 100100

struct vertex
{
    int index, lowlink;
    bool onStack;
    list<int> vecini;
};

vertex graf[MX];
int n,m, Index, S[MX], k, n_scc;
list<int> SCC[MX];

void strongconnect(int v)
{
    graf[v].index= Index;
    graf[v].lowlink= Index;
    graf[v].onStack= true;
    Index++;
    S[++k]= v;

    for (list<int>::iterator w= graf[v].vecini.begin(); w != graf[v].vecini.end(); ++w )
        if ( graf[*w].index == 0 )
        {
            strongconnect(*w);
            graf[v].lowlink= min( graf[v].lowlink, graf[*w].lowlink );
        }
        else
            if ( graf[*w].onStack )
                graf[v].lowlink= min(graf[v].lowlink, graf[*w].index);

    if ( graf[v].lowlink == graf[v].index ) // i am in the root of the SCC, give 'em hell
    {
        n_scc++;
        int w;
        do
        {
            w= S[k--];
            SCC[n_scc].push_back(w);
            graf[w].onStack= false;
        }
        while ( w != v );
    }
}

int main()
{
    int i, x,y;

    f1>>n>>m;
    for (i=1; i<=m; i++)
    {
        f1>>x>>y;
        graf[x].vecini.push_back(y);
    }

    Index= 1;

    for (i=1; i<=n; i++)
        if ( !graf[i].index )
            strongconnect(i);

    f2<<n_scc<<"\n";
    for (i=1; i<= n_scc; i++)
    {
        for (list<int>::iterator it= SCC[i].begin(); it != SCC[i].end(); ++it )
            f2<<*it<<" ";
        f2<<"\n";
    }

    f2.close();
    return 0;
}