Cod sursa(job #2428461)

Utilizator bubblegumixUdrea Robert bubblegumix Data 5 iunie 2019 13:48:59
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb

#include<fstream>

using namespace std;
int a[101][101],n,m,i,j,x,y,s[100],p[101],ctc[101],nrc;
ifstream f("a.txt");
ofstream g("b.txt");
void df1(int nod)
{
    int j;
    s[nod]=1;
    for(j=1;j<=n;j++)
        if(a[nod][j]==1&&s[j]==0)
                  df1(j);
}
void df2(int nod)
{
    int j;
    p[nod]=1;
    for(j=1;j<=n;j++)
        if(a[j][nod]==1&&p[j]==0)
                  df2(j);
}


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

    nrc=0;
    for(i=1;i<=n;i++)
        if(ctc[i]==0) //DACA NODUL I NU APARTINE NICIUNEI COMPONENTE CONEXE
         {
             for(j=1;j<=n;j++)
                    s[j]=p[j]=0;//resetez aparitiile
             df1(i);df2(i);
             nrc++;//daca componenta i nu aprtine nicunei componente conexe inseamna ca chiar ea poate sa fie una si verific asta in cele ce urmeaza
             for(j=1;j<=n;j++)
                if(s[j]==1&&p[j]==1)
                      ctc[j]=nrc;//nodul j apartine componentei conexe cu nr de ordine nrc


         }

    g<<nrc<<endl;
    int  pivot=1;
    while(pivot<=nrc)
    {for(i=1;i<=n;i++)
        if(ctc[i]==pivot)
              g<<i<<" ";
        g<<endl;
      pivot++;
    }


return 0;
}