Cod sursa(job #2839148)

Utilizator SlaninaStefanSlanina Stefan SlaninaStefan Data 25 ianuarie 2022 13:20:54
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>
#define NMAX 101

using namespace std;

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

int n, m, start;
bool A[NMAX][NMAX];
bool viz[NMAX];

void citire();
void DFS(int x);

int main()
{
    int i;
    citire();
    for (i=1; i<=n; i++)
    {
        if (!viz[i])
        {
            ///incepe noua componenta conexa
            nrc++;
            DFS(i);
        }
    }
    afisare();
    return 0;
}

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;
    ///vizitez varful x
    int i;
    viz[x]=nrc;
    ///parcurg vecinii lui x
    for (i=1; i<=n; i++)
    {
        if (A[x][i] && !viz[i]) ///x si i sunt varfuri adiacente si i nevizitat
        {
            DFS(i);
        }
    }
}

void afisare()
{
    int i, j;
    fout<<nrc<<'\n';
    for (i=1; i<=nrc; i++)
    {
        for (j=1; j<=n; j++)
        {
            if (viz[j]==i)
                fout<<j<<' ';
        }
        fout<<'\n';
    }
}