Responsive image
Meniu
Toate soluțiile
Soluţii trimise de tine
Compilator online
Ajutor

Dfs

Adăugată de :
sorynsoo
Sursă :
XOR2012
Autor :
-
Grupă :
Mare
Punctaj :
0 pc

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
200 ms
Limită memorie :
16384 kbytes

Fie un graf neorientat conex, având cele N noduri numerotate de la 1 la N. Se realizează parcurgerea în adâncime a grafului pornind din nodul 1. Dacă există mai mulţi adiacenţi ai săi nevizitaţi, atunci se alege ca nod succesor cel de indice cel mai mic. În continuare se respectă aceeaşi regulă, adică dacă nodul curent este x, se alege dintre toate nodurile adiacente cu x şi nevizitate acela de indice minim. Dacă x nu are adiacenţi, se merge înapoi la nodul precedent lui x pentru a se căuta un adiacent nevizitat

 

 

De exemplu, pentru graful din figură, parcurgând graful în adâncime începând cu nodul 1 şi respectând regulile de mai sus, ordinea vizitării nodurilor este: 1, 2, 4, 3, 5  

 

Cerinţa

Scrieţi un program care să determine numărul maxim de muchii care pot fi adăugate grafului astfel încât ordinea de vizitare a nodurilor prin parcurgerea în adâncime să rămână aceeaşi.

 

Date de intrare

Fişierul de intrare conţine pe prima linie un număr natural N reprezentând numărul de noduri din graf. Pe linia a doua se află un singur număr natural M reprezentând numărul muchiilor grafului. Pe următoarele M linii se găsesc câte două numere naturale x şi y, separate printr-un spaţiu, reprezentând câte o muchie din graf.

 

Date de iesire

Fişierul de iesire va conţine un singur număr natural reprezentând numărul maxim de muchii care se pot adăuga grafului astfel încât ordinea parcurgerii în adâncime a nodurilor să fie aceeaşi.

 

Restricţii şi precizări:

  • 3 <= N <= 1000

 

Exemplu

  Date de intrare

  Date de iesire

  Explicaţii

  5

  5

  1 5

  1 3

  2 1

  3 4

  4 2

  4

  Fişierul de intrare corespunde grafului din imagine. Se pot adăuga maximum 4 muchii: (1,4), (2,5), (3,5), (4,5) şi după adăugare, parcurgerea în adâncime pornind din nodul 1 este tot 1, 2, 4, 3, 5


Trimite o solutie

Format: cpp şi c

Selectează runda

Trebuie să fii logat pentru a trimite surse


Indicații rezolvare

Grafuri


Comentarii

Adauga un comentariu: Click !