Mai intai trebuie sa te autentifici.

Cod sursa(job #1774907)

Utilizator PaulStighiStiegelbauer Paul-Alexandru PaulStighi Data 9 octombrie 2016 16:37:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include<fstream>
#include<vector>
#define NMax 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int N,M,k,K;
int Use[NMax],UseT[NMax];
int O[NMax];

vector <int> V[NMax];
vector <int> VT[NMax];
vector <int> CTC[NMax];

void Read()
{
    fin>>N>>M;

    for(int i = 1 ; i <= M ; ++i)
    {
        int a,b;    fin>>a>>b;

        V[a].push_back(b);
        VT[b].push_back(a);
    }
}

void DFS(int nod)
{
    Use[nod] = 1;

    for(int i = 0 ; i < (int) V[nod].size() ; ++i)
    {
        int Vecin = V[nod][i];

        if(!Use[Vecin])
        {
            DFS(Vecin);
        }
    }

    O[++k] = nod;
}

void DFST(int nod)
{
    Use[nod] = 0;
    CTC[K].push_back(nod);

    for(int i = 0 ; i < (int)VT[nod].size() ; ++i)
    {
        int Vecin = VT[nod][i];

        if(Use[Vecin] == 1)
        {
            DFST(Vecin);
        }
    }
}

void Solve()
{
    for(int i = 1 ; i <= N ; ++i)
    {
        if(!Use[i])
        {
            DFS(i);
        }
    }

    for(int i = N ; i >= 1 ; i--)
    {
        if(Use[O[i]] == 1)
        {
            K++;
            DFST(O[i]);
        }
    }
}

void Print()
{
    fout<<K<<"\n";

    for(int i = 1 ; i <= K ; ++i)
    {
        for(int j = 0 ; j < (int) CTC[i].size() ; ++j)
            fout<<CTC[i][j]<<" ";
        fout<<"\n";
    }
}

int main()
{
    Read();
    Solve();
    Print();

    fin.close();
    fout.close();
    return 0;
}