Cod sursa(job #2839174)

Utilizator ElizaRusuRusu Eliza ElizaRusu Data 25 ianuarie 2022 13:30:13
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#define NMAX 101
using namespace std;
ifstream fin ("componenteconexe.in");
ofstream fout ("componenteconexe.out");
///matrice de adiacenta
int n, nrc;
bool A[NMAX][NMAX];
int viz[NMAX];///viz[x] = nr componentei conexe din care face parte vf x
void citire();
void DFS(int x);
void afisare();
int main()
{
    int i;
    citire();
    for(i=1; i<=n; i++)///parcurg toate vf grafului
        if (viz[i]==0)
        {
            ///incepe o noua componenta conexa
            nrc++;
            DFS(i);
        }///vf i este nevizitat

    afisare();
    return 0;
}

void afisare()
{int i, j;
    fout<<nrc<<endl;
    for(i=1; i<=nrc; i++)
        {///afisez vf din componenta conexa cu nr i
        for (j=1; j<=n; j++)
            if (viz[j]==i) fout<<j<<' ';
        fout<<endl;}
}

void citire()
{
    int i, x, y;
    fin>>n;
    while (fin>>x>>y)
    {
        A[x][y]=A[y][x]=1;
    }

}
void DFS(int x)
{
    int i;
    viz[x]=nrc;
    for(i=1; i<=n; i++)
        if(!viz[i] && A[x][i]==1)
            DFS(i);


}