Cod sursa(job #662496)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 16 ianuarie 2012 19:15:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <cstdio>
#include <vector>

#define NMax 100005

using namespace std;

vector <int> G[NMax], GT[NMax];
int N, SCC[NMax], Found[NMax];
bool Used[NMax];
vector <int> Component[NMax];

void Read ()
{
    freopen ("ctc.in", "r", stdin);
    int M;
    scanf ("%d %d", &N, &M);
    for (; M>0; --M)
    {
        int X, Y;
        scanf ("%d %d", &X, &Y);
        G[X].push_back (Y);
        GT[Y].push_back (X);
    }
}

void Print ()
{
    freopen ("ctc.out", "w", stdout);
    printf ("%d\n", SCC[0]);
    for (int i=1; i<=SCC[0]; ++i)
    {
        for (int j=0; j<Component[i].size (); ++j)
        {
            printf ("%d ", Component[i][j]);
        }
        printf ("\n");
    }
}

inline void DFP (int X)
{
    Used[X]=true;
    for (vector <int> :: iterator V=G[X].begin (); V!=G[X].end (); ++V)
    {
        if (!Used[*V])
        {
            DFP (*V);
        }
    }
    Found[++Found[0]]=X;
}

inline void DFM (int X, int C)
{
    SCC[X]=C;
    for (vector <int> :: iterator V=GT[X].begin (); V!=GT[X].end (); ++V)
    {
        if (!SCC[*V])
        {
            DFM (*V, C);
        }
    }
    Component[C].push_back (X);
}

void Kosaraju ()
{
    for (int i=1; i<=N; ++i)
    {
        if (!Used[i])
        {
            DFP (i);
        }
    }
    for (int i=Found[0]; i>0; --i)
    {
        if (!SCC[Found[i]])
        {
            ++SCC[0];
            DFM (Found[i], SCC[0]);
        }
    }
}

int main()
{
    Read ();
    Kosaraju ();
    Print ();
    return 0;
}