Se consideră un graf neorientat cu n vârfuri și m muchii și de asemenea un vârf X.

Cerinţa

Să se afișeze vârfurile vizitate în urma parcurgerii în adâncime (Depth First Search) a grafului, pornind din vârful X.

Date de intrare

Fişierul de intrare dfs.in conţine pe prima linie trei numere naturale n, m, X, având următoarea semnificație: n este numărul de noduri, m este numărul de muchii din graf, iar X este vârful din care se începe parcurgerea. Următoarele m linii conțin câte două numere i j cu semnificația că există muchie între i și j .

Date de ieşire

Fişierul de ieşire dfs.out va conţine pe prima linie vârfurile vizitate în urma parcurgerii în adâncime a grafului, aceasta începând din vârful X.

Restricţii şi precizări

2 <= n <= 100
1 <= m <= n*(n-1)/2
dacă în timpul parcurgerii, la un moment dat vârful curent al grafului este Y, vecinii nevizitați ai lui Y se vor analiza în ordine crescătoare.

Exemplu

dfs.in

dfs.out

3 1 2 4 6 5 7

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema DFS:

#include <iostream>
#include <fstream>
#include <cassert>
using namespace std;

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

int n , a[105][105], v[205];

void dfs(int X)
{
    fout << X << " ";
    v[X] = 1;
    for(int i =1 ; i <= n ; ++i)
        if(a[X][i] == 1 && v[i] == 0)
            dfs(i);
}

int main()
{
    int i , j , m, X;
    fin >> n >> m >> X;
    while(m > 0)
    {
        fin >> i >> j;
        a[i][j] = a[j][i] = 1;
        m --;
    }
    dfs(X);
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #539 DFS

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #539 DFS de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #539 DFS