Cod sursa(job #2117200)

Utilizator IustinPetrariuIustinian Petrariu IustinPetrariu Data 28 ianuarie 2018 17:46:48
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
 using namespace std;
 ifstream fin("ctc.in");
 ofstream fout("ctc.out");

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

void citire()
{
    int x,y;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>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++;
        }
    fout<<nrc-1<<endl;
  for(int i =1 ; i <= nrc-1 ; i++)
  {
      for(int j =1 ; j <= n ; j++)
        if(suc[j]==i)
      {
          fout<<j<<" ";
      }
      fout<<endl;
  }
    return 0;
}