Cod sursa(job #2839170)

Utilizator ioana__leseLese Ioana ioana__lese Data 25 ianuarie 2022 13:27:59
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#define NMAX 101
using namespace std;
ifstream fin ("componenteconexe.in");
ofstream fout ("componenteconexe.out");
int n,m,start,nrc,x,y;
int a[NMAX][NMAX];
bool v[NMAX];
void citire();
void DFS (int x, int val);

int main()
{
    fin >> n;
    while(fin >> x >> y)
    {
        a[x][y] = a[y][x] = 1;
        m++;
    }
    for(int i = 1 ; i <= n ; i++)
        if(v[i] == 0) DFS(i , nrc + 1) , nrc++;
    fout << nrc << '\n';
    for(int i = 1 ; i <= nrc ; i++)
    {
        for(int j = 1 ; j <= n ; j++)
            if(i == v[j]) fout << j << " ";
        fout << '\n';
    }
}

void DFS(int x , int val)
{
    v[x] = val;
    for(int i = 1 ; i <= n ; i++)
        if(!v[i] && a[x][i] == 1)
        {
            DFS(i , val);
            v[i] = val;
        }
}