Cod sursa(job #1876544)

Utilizator razboi4Manole Iulian razboi4 Data 12 februarie 2017 14:15:16
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

#define IT vector < int > :: iterator
#define NMAX 100005

using namespace std;

vector < int > gr[NMAX];
vector < int > gr2[NMAX];
vector < int > gr3[NMAX];
vector < int > postordine;

bool viz[50001];

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

    for (IT it = gr[x].begin(); it != gr[x].end(); ++ it)
      if (!viz[*it])
        DFS(*it);

    postordine.push_back(x);
}

void DFST(int x, int y)
{
    viz[x] = 0;
    gr3[y].push_back(x);

    for (IT it = gr2[x].begin(); it != gr2[x].end(); ++ it)
      if (viz[*it])
        DFST(*it, y);
}

int main()
{
    int n, a, b, m;

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

    fin >> n >> m;

    int nr = 0;

    for (int i = 1 ; i <= m; ++ i)  {
      fin >> a >> b;
      gr[a].push_back(b);
      gr2[b].push_back(a);
    }

    for (int i = 1; i <= n; ++ i)
      if (!viz[i])
        DFS(i);

    vector < int > :: reverse_iterator it5;

    for (it5 = postordine.rbegin(); it5 != postordine.rend(); ++ it5)
      if (viz[*it5]) {
        ++ nr;
        DFST(*it5, nr);
    }

    fout << nr << "\n";

    for (int i = 1; i <= nr; ++ i) {
      for (IT it = gr3[i].begin(); it != gr3[i].end(); ++ it)
        fout << *it << " ";

      fout << "\n";
    }

    return 0;
}