Cod sursa(job #1553698)

Utilizator felipeGFilipGherman felipeG Data 20 decembrie 2015 12:58:12
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include<fstream>
#define N 110
using namespace std;

ifstream f ("ctc.in");
ofstream g ("ctc.out");

int a[N][N], n, m, nrc, suc[N], pred[N];

void citire()
{
    int x,y;
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        f >> x >> y;
        a[x][y] = 1;
    }
}

void dfsuc (int nod)
{
    int k;
    suc[nod] = nrc;
    for (k = 1; k <= n; k++)
       if(a[nod][k] == 1 && suc[k] == 0)
          dfsuc(k);
}

void dfpred (int nod)
{
    int k;
    pred[nod] = nrc;
    for (k = 1; k <= n; k++)
       if(a[k][nod] == 1 && pred[k] == 0)
         dfpred(k);
}

int main()
{
    citire();
    nrc = 1;
    for (int i = 1;i <= n; i++)
       if (suc[i] == 0)
       {
        dfsuc(i);
        dfpred(i);
        for (int j = 1; j <= n; j++)
          if (suc[j] != pred[j])
            suc[j] = pred[j] = 0;
        nrc++;
       }

    g << nrc - 1 << endl;
    for (int i = 1; i < nrc; i++)
    {
      for (int j = 1; j <= n; j++)
        if (suc[j] == i)
          g << j << " ";
      g << endl;
    }
}