Cod sursa(job #2346413)

Utilizator corina_dimitriuDimitriu Corina corina_dimitriu Data 17 februarie 2019 17:39:40
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
#define DMAX 100005

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int d[105][105],uz[DMAX],rez[105][105];
int N,M,nr;
void citire();
void afisare();
void DFS(int nod);
int main()
{int k,i,j;
    citire();
    for(k=1;k<=N;k++)
        for(i=1;i<=N;i++)
            for(j=1;j<=N;j++)
                if(!d[i][j])
                   d[i][j]=d[i][k]*d[k][j];
    for(i=1;i<=N;i++)
        for(j=i+1;j<=N;j++)
            if(i==j||d[i][j]!=d[j][i]) d[i][j]=d[j][i]=0;
    for(i=1;i<=N;i++)
        if(!uz[i])
          {
           nr++;
           rez[nr][++rez[nr][0]]=i;
           uz[i]=1;
           DFS(i);
          }
    afisare();
    return 0;
}
void citire()
{int ei,ef,i;
    fin>>N;
    fin>>M;
    for(i=1;i<=M;i++)
       {fin>>ei>>ef;
        d[ei][ef]=1;
       }
}
void afisare()
{int i,j;
 fout<<nr<<'\n';
   for(i=1;i<=nr;i++)
      {for(j=1;j<=rez[i][0];j++)
           fout<<rez[i][j]<<' ';
       fout<<'\n';
      }

}
void DFS(int nod)
{int vecin;
    for(vecin=1;vecin<=N;vecin++)
        if(!uz[vecin]&&d[nod][vecin]==1)
           {uz[vecin]=1;
            rez[nr][++rez[nr][0]]=vecin;
            DFS(vecin);
           }
}