Cod sursa(job #596548)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 17 iunie 2011 18:36:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

vector <int> G[100005], C;
stack <int> Stack;
vector < vector <int> > CTC;
int N, Index[100005], CIndex, LowestI[100005];
bool InStack[100005];

void Read ()
{
    ifstream fin ("ctc.in");
    int M, X, Y;
    fin >> N >> M;
    for (; M>0; --M)
    {
        fin >> X >> Y;
        G[X].push_back (Y);
    }
    fin.close ();
}

void Type ()
{
    ofstream fout ("ctc.out");
    unsigned i, j;
    fout << CTC.size () << "\n";
    for (i=0; i<CTC.size (); ++i)
    {
        for (j=0; j<CTC[i].size (); ++j)
        {
            fout << CTC[i][j] << " ";
        }
        fout << "\n";
    }
    fout.close ();
}

inline int Min (int a, int b)
{
    if (a<b)
    {
        return a;
    }
    return b;
}

void DetCTC (int X)
{
    int Y;
    do
    {
        Y=Stack.top ();
        C.push_back (Y);
        InStack[Y]=false;
        Stack.pop ();
    }
    while (Y!=X);
    CTC.push_back (C);
    C.clear ();
}

void Tarjan (int X)
{
    vector <int> :: iterator V;
    Index[X]=CIndex;
    LowestI[X]=CIndex;
    CIndex++;
    Stack.push (X);
    InStack[X]=true;
    for (V=G[X].begin (); V!=G[X].end (); ++V)
    {
        if (Index[*V]==-1)
        {
            Tarjan (*V);
            LowestI[X]=Min (LowestI[X], LowestI[*V]);
        }
        else
        {
            if (InStack[*V]==true)
            {
                LowestI[X]=Min (LowestI[X], LowestI[*V]);
            }
        }
    }
    if (Index[X]==LowestI[X])
    {
        DetCTC (X);
    }
}

int main()
{
    int i;
    Read ();
    for (i=1; i<=N; ++i)
    {
        Index[i]=-1;
    }
    for (i=1; i<=N; ++i)
    {
        if (Index[i]==-1)
        {
            Tarjan (i);
        }
    }
    Type ();
    return 0;
}