== include(page="template/taskheader" task_id="shuffle2") ==
Fie G un graf orientat aciclic fără costuri pe muchii. În această problemă vom analiza ce se întâmplă dacă folosim o pargurgere în adâncime pentru a calcula drumul de lungime minimă dintre nodul 1 şi nodul N. Mai exact, vom rula algoritmul descris de următoarea secvenţă de pseudocod:
Fie $G$ un graf **orientat aciclic** fără costuri pe muchii. În această problemă vom analiza ce se întâmplă dacă folosim o pargurgere în adâncime pentru a calcula drumul de lungime minimă dintre nodul **$1$** şi nodul **$N$**. Mai exact, vom rula algoritmul descris de următoarea secvenţă de pseudocod:
== code(cpp) |
== code(python) |
viz[x] = 0, oricare ar fi x
dist[1] = 0
DFS(nod):
viz[nod] = 1
pentru toti vecinii v din lista de adiacenţă a lui nod:
daca viz[v] este 0:
dist[v] = dist[nod] + 1
DFS(v)
viz[nod] = 1
pentru toti vecinii v din lista de adiacenţă a lui nod:
daca viz[v] este 0:
dist[v] = dist[nod] + 1
DFS(v)
DFS(1)
afişează dist[N]
==
h2. Date de intrare
Formarea listelor de adiacenţă ale grafului urmează următorul pseudocod (unde $lista[x]$ reprezintă lista vecinilor lui $x$):
Fişierul de intrare $shuffle2.in$ ...
== code(python) |
lista[x] = [], oricare ar fi x
h2. Date de ieşire
citeste n, m
pentru i de la 1 la m:
citeste a, b
adauga b la sfarsitul lui lista[a]
==
În fişierul de ieşire $shuffle2.out$ ...
Bineînţeles, acest algoritm nu este întotdeauna corect, deoarece distanţa calculată depinde de ordinea în care sunt procesaţi vecinii unui nod în timpul citirii.
De exemplu, dacă la construirea grafului se citeşte întâi muchia $(1 → 2)$ şi apoi muchia $(1 → 3)$, atunci când vecinii lui $1$ sunt prelucraţi, primul vecin va fi $2$, iar următorul va fi $3$. Aşadar, distanţa calculată cu primul algoritm de mai sus poate fi diferită, în funcţie de ordinea în care sunt adăugate muchiile de la citire. Prin urmare, pentru un graf dat, suntem curioşi pentru câte dintre cele **$M!$** permutări ale muchilor lui **$G$**, algoritmul DFS va da distanţa minimă.
h2. Restricţii
h2. Date de intrare
* $... ≤ ... ≤ ...$
Pe prima linie a fişierului de intrare $shuffle2.in$ se vor afla două numere naturale **$N$**, numărul de noduri, şi **$M$**, numărul de muchii. Pe următoarele **$M$** linii se vor afla două numere **$x$** si **$y$**, reprezentând faptul că în graf există muchia orientată de la **$x$** la **$y$**.
h2. Exemplu
h2. Date de ieşire
table(example). |_. shuffle2.in |_. shuffle2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
Pe prima linie a fişierului de ieşire $shuffle2.out$ se va afişa un singur număr, care reprezintă numărul de permutări acceptabile modulo **$1000000007$**.
h3. Explicaţie
h2. Restricţii
...
* $1 ≤ N ≤ 100 000$.
* $1 ≤ M ≤ 200 000$.
* Se garantează că pentru teste în valoare de $10%$ din punctaj, $N, M ≤ 10$.
* Se garantează că pentru teste în valoare de $25%$ din punctaj, $N <= 20, M ≤ 60$.
* Se garantează că pentru teste în valoare de $60%$ din punctaj, $N <= 1400, M ≤ 4000$.
* Se garantează că o muchie nu va apărea de două ori în fişierul de intrare.
* Se garantează că fiecare muchie aparţine cel puţin unui drum de la $1$ la $N$.
h2. Exemple
table(example). |_. shuffle2.in |_. shuffle2.out |_. Explicatii |
| 3 3
1 2
1 3
2 3
| 3
| Cele trei permutări pentru care se obţine
distanţa minimă sunt:
(1→3) (1→2) (2→3)
(1→3) (2→3) (1→2)
(2→3) (1→3) (1→2) |
| 4 5
1 2
1 3
2 3
2 4
3 4
| 90
| Distanţa minimă de la 1 la 4 este 2 şi sunt 90
de permutări ale celor 5 muchii care dau această
distanţă minimă. |
| 7 11
2 4
3 2
1 3
2 6
6 7
4 5
4 6
6 5
5 7
2 5
3 4
| 24948000
| - |
== include(page="template/taskfooter" task_id="shuffle2") ==
