Universal Cup Judging System

Universal Cup

시간 제한: 2.0 s 메모리 제한: 1024 MB 총점: 100 난이도: [표시] 해킹 가능 ✓
통계

נזכיר את אלגוריתם טארג'ן לחישוב נקודות ההפרדה (הנקראות גם צומתי חתך) בגרף לא מכוון, שהפסאודו-קוד שלו מוצג באלגוריתם 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

שימו לב שבפסאודו-קוד, $\textit{adj}[i]$ הוא המערך המכיל את כל הצמתים השכנים לצומת $i$, $\textit{parent}$ הוא מערך שבו הערך ההתחלתי של כל איבר הוא $\text{null}$, ו-$\textit{visited}$ הוא מערך שבו הערך ההתחלתי של כל איבר הוא $\text{false}$.

חלק מהסטודנטים מתקשים להבין את האלגוריתם הזה, במיוחד משורה $19$ עד שורה $22$. הם אינם מבינים מדוע אלגוריתם טארג'ן צריך לחשב את הערך של $\textit{low}[i]$ בצורה שונה, ועלולים לזכור גרסה שגויה של האלגוריתם. נקרא לגרסה השגויה הזו אלגוריתם טראיאן, המוצג באלגוריתם 2. שימו לב שהאלגוריתמים טארג'ן וטראיאן כמעט זהים, למעט שמות הפונקציות ו-$4$ השורות משורה $19$ עד שורה $22$.

בהינתן גרף קשיר לא מכוון עם $n$ צמתים ו-$m$ קשתות, קבעו עבור כל צומת $u$ האם קיימים צומת $v$ ומערך דו-ממדי ($2$-ממדי) $\textit{adj}$ ($\textit{adj}$ חייב לייצג את הגרף הנתון) כך ש-$\textsc{Tarjan}(v, 0)$ ו-$\textsc{Trajan}(v, 0)$ מפיקים תוצאות שונות עבור הצומת $u$ (כלומר, אלגוריתם טארג'ן קובע שהצומת $u$ הוא נקודת הפרדה בעוד שאלגוריתם טראיאן אינו קובע זאת, או להפך).

קלט

ישנם מספר מקרי בדיקה. השורה הראשונה של הקלט מכילה מספר שלם $T$ ($1 \le T \le 10^4$) המציין את מספר מקרי הבדיקה. עבור כל מקרה בדיקה:

השורה הראשונה מכילה שני מספרים שלמים $n$ ו-$m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$) המציינים את מספר הצמתים והקשתות בגרף הנתון.

ב-$m$ השורות הבאות, השורה ה-$i$ מכילה שני מספרים שלמים $u_i$ ו-$v_i$ ($1 \le u_i, v_i \le n$) המציינים שישנה קשת המחברת בין הצמתים $u_i$ ו-$v_i$ בגרף.

מובטח שהגרף הנתון קשיר ושאין בו לולאות עצמיות או קשתות כפולות. כמו כן, לא סכום ערכי $n$ ולא סכום ערכי $m$ בכל מקרי הבדיקה יעלו על $10^6$.

פלט

עבור כל מקרה בדיקה הדפיסו שורה אחת המכילה מספרים שלמים המופרדים ברווח בודד בסדר עולה. כל מספר שלם הוא צומת שעבורו אלגוריתמי טארג'ן וטראיאן עשויים להפיק תוצאות שונות. אם אין צמתים כאלה, הדפיסו במקום זאת Empty בשורה אחת.

דוגמה

קלט לדוגמה 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

פלט לדוגמה 1

3 6 9
Empty

הערה

עבור מקרה הבדיקה הראשון בדוגמה:

  • עבור $u = 3$ התבוננו ב-$v = 1$ וב-$\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]]$.
  • עבור $u = 6$ התבוננו ב-$v = 4$ וב-$\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]]$.
  • עבור $u = 9$ התבוננו ב-$v = 7$ וב-$\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]]$.

שימו לב שכל מערכי $\textit{adj}$ בהסבר ממוספרים החל מ-$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.