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