Problem graf


Se ştie că într-un graf neorientat conex, între oricare două vârfuri există cel puţin un lanţ iar lungimea unui lanţ este egală cu numărul muchiilor care-l compun. Definim noţiunea lanţ optim între două vârfuri X şi Y ca fiind un lanţ de lungime minimă care are ca extremităţi vârfurile X şi Y. Este evident că între oricare două vârfuri ale unui graf conex vom avea unul sau mai multe lanţuri optime, depinzând de configuraţia grafului.

Cerinţă:

Fiind dat un graf neorientat conex cu N vârfuri etichetate cu numerele de ordine 1,2,…,N şi două vârfuri ale sale notate X şi Y (1≤X,Y≤N, X≠Y ), se cere să scrieţi un program care determină vârfurile care aparţin tuturor lanţurilor optime dintre X şi Y.

Date de intrare:

Fişierul graf.in conţine

  • pe prima linie patru numere naturale reprezentând: N (numărul de vârfuri ale grafului), M (numărul de muchii), X şi Y (cu semnificaţia din enunţ).
  • pe următoarele M linii câte două numere naturale nenule \(A_i,B_i\) (\(1≤A_i,B_i≤N, Ai ≠ Bi\) , pentru 1≤i≤M ) fiecare dintre aceste perechi de numere reprezentând câte o muchie din graf.

Date de ieşire:

Fişierul graf.out va conţine

  • pe prima linie, numărul de vârfuri comune tuturor lanţurilor optime dintre X şi Y;
  • pe a doua linie, numerele corespunzătoare etichetelor acestor vârfuri, dispuse în ordine crescătoare; între două numere consecutive de pe această linie se va afla câte un spaţiu.

Restricţii:

  • 2≤N≤7500; 1≤M≤14000
  • pentru 50% din teste N≤200

Exemple

graf.in

6 7 1 4
1 2
1 3
1 6
2 5
3 5
5 6
5 4

graf.out

3
1 4 5

graf.in

3 2 1 3
1 2
3 1

graf.out

2
1 3

General info

ID: 49

Upload: liviu

Input: graf.in/graf.out

Memory limit: 16MB/8MB

Time limit: 0.03s

Author: Victor Manz

Source: OJI 2006 XI-XII: Problema 1

Submissions

Special Submissions