Cod sursa(job #1368576)

Utilizator Darius15Darius Pop Darius15 Data 2 martie 2015 18:37:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

int f[100001], s[200001], t, n, m, nctc;
bool viz[100001];
ifstream fi("ctc.in");
//ifstream fi("ftclr.in");
ofstream fout("ctc.out");
vector <int> v[100001], vt[100001], scc[100001];

void dffinal(int i) {
  int c;

  viz[i] = true; t++;
  for (c = 0; c < v[i].size(); c++)
    if (not viz[v[i][c]])            // Nu a fost vizitat.
      dffinal(v[i][c]);
  t++; f[i] = t; s[t] = i;
}

void dfsc(int i) {
  int c;

  scc[nctc].push_back(i);            // Retinem nodul.
  viz[i] = true;                     // Il consideram vizitat.
  for (c = 0; c < vt[i].size(); c++)
    if (not viz[vt[i][c]])           // Nu a fost vizitat.
      dfsc(vt[i][c]);                // Parcurgem in adancime.
}

int main()
{
    int x, y, i, nc, l, c;

    fi >> n >> m;
    for (i = 1; i <= m; i++)
    {
        fi >> x >> y;
        v[x].push_back (y);
        vt[y].push_back (x);
    }
    t = 0;
    for (i = 1; i <= n; i++) // Determinam timpii finali.
        if (not viz[i])
            dffinal(i);
    memset(viz, 0, 100001 * sizeof(bool)); // Reinitializam pentru parcurgerea care urmeaza.
    for (l = t; l >= 0; l--)   // Parcurgem sirul sortat al nodurilor.
    {
        if (s[l] != 0)           // S-ar putea ca locului l sa nu ii corespunda un nod.
        {
            nc = s[l];             // nodul curent
            if (not viz[nc])       // Nu a fost vizitat.
            {
                nctc++;              // inca o componenta
                dfsc(nc);            // Parcurgem o componenta.
            }
        }
    }
    fout << nctc << '\n';
    for (c = 1; c <= nctc; c++)   // Pentru fiecare componenta
    {
        for (n = 0; n < scc[c].size(); n++) // nodul din componenta
            fout << scc[c][n] << ' ';
        fout << '\n';
    }
    return 0;
}