Cod sursa(job #2450651)

Utilizator bubblegumixUdrea Robert bubblegumix Data 23 august 2019 22:53:21
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include<iostream>
#include<fstream>
using namespace std;
int a[101][101],n,m,i,j,x,y,s[100],p[101],ctc[101],nrc,sol[100][100];

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

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;
    }


/*    cout<<"Matricea de adiacenta e:"<<endl;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl<<endl;*/
    nrc=0;
    int k=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
                      sol[nrc][++k]=j;
                }
            k=0;
         }

    g<<nrc<<'\n';
    for(i=1;i<=nrc;i++)
    {
        for(j=1;j<=n;j++)
           if(sol[i][j]==0)
                break;
            else
                g<<sol[i][j]<<" ";
        g<<'\n';
    }






return 0;
}