Cod sursa(job #1994421)

Utilizator CammieCamelia Lazar Cammie Data 24 iunie 2017 22:09:27
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <vector>

#define MAXN 100002
#define MAXM 200002

using namespace std;

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

vector <int> G[MAXM], Q[MAXM];
int pred[MAXN], postordine[MAXN], viz[MAXN];
int n, m, contor, x, y, nn;

vector <int> sol[MAXN];

inline void Read()
{
    fin >> n >> m;

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

        G[x].push_back(y); ///construiesc graful normal
        Q[y].push_back(x); ///construiesc graful transpus
    }
}

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

    for (vector <int> :: iterator i = G[nod].begin(); i != G[nod].end(); i++)
    {
        if (!viz[*i])
        {
            DFS(*i);
        }
    }
    postordine[++nn] = nod;
}

inline void DFST(int nod)
{
    sol[contor].push_back(nod);
    viz[nod] = 0;

    for (vector <int> :: iterator i = Q[nod].begin(); i != Q[nod].end(); i++)
    {
        if (viz[*i])
            DFST(*i);
    }
}

inline void Solve()
{
    for (int i = 1; i <= n; i++)
    {
        if (!viz[i]) ///construiesc componente conexe
            DFS(i);
    }

    for (int i = n; i > 0; i--)
    {
        if (viz[postordine[i]])
        {
            contor++;
            DFST(postordine[i]);
        }
    }

    fout << contor << "\n";

    for (int i = 1; i <= contor; i++)
    {
        for (vector <int> :: iterator j = sol[i].begin(); j != sol[i].end(); j++)
        {
            fout << *j << " ";
        }

        fout << "\n";
    }
}

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

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