Cod sursa(job #2368215)

Utilizator calinfloreaCalin Florea calinflorea Data 5 martie 2019 14:36:49
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>
#define NMax 100006

using namespace std;

ifstream fin ("ctc.in");
ofstream fout ("ctc.out");

vector <int> L[NMax];
vector <int> G[NMax];
int n, m, k, nrcc;
bool viz[NMax];
int sir[NMax];

void Read ()
{
    int x, y;
    fin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y;

        L[x].push_back (y);
        G[y].push_back (x);
    }
}

void DFS1 (int nod)
{
    int i;

    viz[nod] = 1;

    for (int j = 0; j < L[nod].size(); j++)
    {
        i = L[nod][j];
        if (!viz[i])
            DFS1(i);
    }
    sir[++k] = nod;
}

void DFS2 (int nod)
{
    int i;
    viz[nod] = 1;

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

        if (!viz[i])
            DFS2(i);
    }

    L[nrcc].push_back (nod);
}

void Initilizare ()
{
    for (int i = 1; i <= n; i++)
        viz[i] = 0;
}

void Solve ()
{
    for (int i = 1; i <= n; i++)
        if (!viz[i])
            DFS1(i);

    Initilizare();

    for (int i = k; i >= 1; i--)
        if (!viz[sir[i]])
        {
            nrcc++;
            L[nrcc].clear();
            DFS2(sir[i]);
        }

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

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

    return 0;
}