Cod sursa(job #870636)

Utilizator danutbodbodnariuc danut danutbod Data 3 februarie 2013 19:12:30
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
//2
//1 2 3
//4 5 6 7 8
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");//modif
int n, m, nrc, a[4000][4000], suc[4000], pred[4000];
bool p[2000];
void df (int nod, int nrc)
{
  int i;
  suc[nod] = nrc;
  for (i = 1; i <= n; i++)
    if (a[nod][i] == 1 and suc[i] == 0) df(i,nrc);
}

void dft (int nod,int nrc) //df transpus
{
  int i;
  pred[nod]=nrc;
  for (i = 1; i <= n; i++)
    if (a[i][nod] == 1 and pred[i] == 0) dft(i,nrc);
}

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

for (i = 1; i <= n; i++)
    if (suc[i]==0)
    {
      nrc++;
      df(i,nrc);
      dft(i,nrc);
      for (j = 1; j <= n; j++)
        if (suc[j]!=pred[j]) suc[j]=pred[j]=0;
    }
  g << nrc << endl;

for (c = 1; c <= nrc; c++)
  {
    for (i = 1; i <= n; i++)
      if(suc[i]==c) g << i << ' ';
    g << endl;
  }
//   for (i = 1; i <= n; i++) g<<suc[i]<<' ';g<<endl;
//  for (i = 1; i <= n; i++) g<<pred[i]<<' ';g<<endl;
  return 0;
}