חישוביות 2024 תרגיל 4 שאלה 4 - שפת הגרפים המכוונים הקשירים חזק היא NL שלימה

כפי שהציעו בסרטון, אפשר לפתור את סעיף א בצורה יותר פשוטה על ידי מעבר סדרתי על כל הקודקודים והפעלת STCONN לכל זוג. ברגע שאחת מההפעלות דחתה, נדחה. אחרת, נקבל.
מי שרוצה לרענן את זכרונו בהקשר של סיבוכיות מקום -
הגדרת L ו NL:
• הרצאה 10 - הגדרת L ו NL
שפות NL שלימות:
• הרצאה 10 - הגדרת רדוקצ...
הגדרת STCONN:
• הרצאה 10 - ST-CONN שיי...
משפט אימרמן על קצה המזלג:
• הרצאה 11 - הצגה ומוטיב...