Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

Rappelons l'algorithme de Tarjan permettant de calculer les points d'articulation (également appelés sommets de coupure) dans un graphe non orienté, dont le pseudo-code est présenté dans l'Algorithme 1.

Algorithm 1 The Correct Tarjan Algorithm
 1: function TARJAN(i, d)
 2:     visited[i] <- true
 3:     depth[i] <- d
 4:     low[i] <- d
 5:     childCount <- 0
 6:     isArticulation <- false
 7:
 8:     for each j in adj[i] do
 9:         if j = parent[i] then
10:             continue
11:         end if
12:         if not visited[j] then
13:             parent[j] <- i
14:             TARJAN(j, d + 1)
15:             childCount <- childCount + 1
16:             if low[j] >= depth[i] then
17:                 isArticulation <- true
18:             end if
19:             low[i] <- min(low[i], low[j])
20:         else
21:             low[i] <- min(low[i], depth[j])
22:         end if
23:     end for
24:     if (parent[i] != null and isArticulation)
        or (parent[i] = null and childCount > 1)
        then
25:         Output i as articulation point
26:     end if
27: end function
Algorithm 2 The Incorrect Trajan Algorithm
 1: function TRAJAN(i, d)
 2:     visited[i] <- true
 3:     depth[i] <- d
 4:     low[i] <- d
 5:     childCount <- 0
 6:     isArticulation <- false
 7:
 8:     for each j in adj[i] do
 9:         if j = parent[i] then
10:             continue
11:         end if
12:         if not visited[j] then
13:             parent[j] <- i
14:             TRAJAN(j, d + 1)
15:             childCount <- childCount + 1
16:             if low[j] >= depth[i] then
17:                 isArticulation <- true
18:             end if
19:         end if
20:         low[i] <- min(low[i], low[j])
21:
22:
23:     end for
24:     if (parent[i] != null and isArticulation)
        or (parent[i] = null and childCount > 1)
        then
25:         Output i as articulation point
26:     end if
27: end function

Notez que dans le pseudo-code, $\textit{adj}[i]$ est le tableau contenant tous les sommets adjacents au sommet $i$, $\textit{parent}$ est un tableau dont chaque élément vaut initialement $\text{null}$, et $\textit{visited}$ est un tableau dont chaque élément vaut initialement $\text{false}$.

Certains étudiants peuvent avoir du mal à comprendre cet algorithme, en particulier de la ligne $19$ à la ligne $22$. Ils ne comprennent pas pourquoi l'algorithme de Tarjan doit calculer la valeur de $\textit{low}[i]$ différemment, et peuvent retenir une version erronée de l'algorithme. Appelons cette version erronée l'algorithme de Trajan, présentée dans l'Algorithme 2. Remarquez que les algorithmes de Tarjan et de Trajan sont presque identiques, à l'exception des noms de fonctions et des $4$ lignes allant de la ligne $19$ à la ligne $22$.

Étant donné un graphe connexe non orienté à $n$ sommets et $m$ arêtes, déterminez pour chaque sommet $u$ s'il existe un sommet $v$ et un tableau bidimensionnel ($2$-D) $\textit{adj}$ ($\textit{adj}$ devant représenter le graphe donné) tels que $\textsc{Tarjan}(v, 0)$ et $\textsc{Trajan}(v, 0)$ produisent des résultats différents sur le sommet $u$ (c'est-à-dire que l'algorithme de Tarjan déclare que le sommet $u$ est un point d'articulation alors que l'algorithme de Trajan ne le fait pas, ou inversement).

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 10^4$) indiquant le nombre de cas de test. Pour chaque cas de test :

La première ligne contient deux entiers $n$ et $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$) indiquant le nombre de sommets et d'arêtes dans le graphe donné.

Pour les $m$ lignes suivantes, la $i$-ème ligne contient deux entiers $u_i$ et $v_i$ ($1 \le u_i, v_i \le n$) indiquant qu'il existe une arête reliant les sommets $u_i$ et $v_i$ dans le graphe.

Il est garanti que le graphe donné est connexe et qu'il ne comporte ni boucles ni arêtes multiples. De plus, ni la somme des $n$ ni la somme des $m$ sur l'ensemble des cas de test ne dépasseront $10^6$.

Sortie

Pour chaque cas de test, affichez une ligne contenant des entiers séparés par un espace dans l'ordre croissant. Chaque entier est un sommet sur lequel les algorithmes de Tarjan et de Trajan peuvent produire des résultats différents. S'il n'existe aucun tel sommet, affichez Empty sur une ligne à la place.

Exemple

Entrée d'exemple 1

2
9 12
1 3
2 3
1 2
3 6
6 9
9 3
4 6
5 6
4 5
7 9
8 9
7 8
2 1
1 2

Sortie d'exemple 1

3 6 9
Empty

Note

Pour le premier cas de test de l'exemple :

  • Pour $u = 3$, considérez $v = 1$ et $\textit{adj} = [[3, 2], [3, 1], [1, 2, 6, 9], [6, 5], [6, 4], [4, 5, 3, 9], [9, 8], [9, 7], [7, 8, 3, 6]]$.
  • Pour $u = 6$, considérez $v = 4$ et $\textit{adj} = [[2, 3], [1, 3], [9, 6, 2, 1], [6, 5], [6, 4], [4, 5, 3, 9], [9, 8], [9, 7], [7, 8, 3, 6]]$.
  • Pour $u = 9$, considérez $v = 7$ et $\textit{adj} = [[2, 3], [1, 3], [9, 6, 2, 1], [5, 6], [4, 6], [9, 3, 5, 4], [9, 8], [9, 7], [7, 8, 3, 6]]$.

Notez que tous les tableaux $\textit{adj}$ de l'explication sont indexés à partir de $1$.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.