Cod sursa(job #2967220)

Utilizator Stefan_Raluca_IoanaStefan Raluca-Ioana Stefan_Raluca_Ioana Data 19 ianuarie 2023 10:39:31
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#define NMAX 102

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int n, nrc;
int G[NMAX][NMAX];
int uz[NMAX];///uz[i]=x daca i a fost deja vizitat in componenta conexa x
int d[NMAX];///d[i]=gradul exterior al varfului i
void citire();
void afisare();
void dfs(int x);
int main()
{
    int i;
    citire();
    for(i=1; i<=n; i++)
        if(!uz[i])///am identificat o noua componenta conexa
        {
            nrc++;
            dfs(i);
        }
    afisare();
    return 0;
}
void citire()
{
    int x, y;
    fin>>n;
    while(fin>>x>>y)
    {
        ///adaug pe x in lista de adiacenta a lui y
        G[y][d[y]++]=x;
        ///adaug pe y in lista de adiacenta a lui x
        G[x][d[x]++]=y;
    }
}
void dfs(int x)
///parcurg DFS graful incepand din varful x
{
    int i;
    uz[x]=nrc; ///il marchez pe x ca vizitat
    ///parcurg toti vecinii lui x in ordinea din lista de adiacenta
    for(i=0; i<d[x]; i++)
        if(!uz[G[x][i]])
            dfs(G[x][i]);
}
void afisare()
{
    int i, j;
    fout<<nrc<<'\n';
    /*for(i=1; i<=nrc; i++)
    {
        ///afiseaza varfurile care sun in componenta conexa cu numarul i
        for(j=1; j<=n; j++)
            if(uz[j]==i)
                fout<<j<<' ';
        fout<<'\n';*/
}