מסילה מכוונת שעוברת דרך קבוצת קודקודים
eliran (guest) 01 Feb 2015 16:18
היי, יש שאלה במבחנים שנותנת לך גרף מכוון, קבוצה של קודקודים ושואלת האם יש מסילה מכוונת שעוברת דרך כולם
רציתי לדעת אם הפתרון שלי נכון-
למצוא את גרף העל ,לסמן באיזה רכיבי קשירות ואז לעשות מיון טפולוגי
אחרי זה אנחנו נריץ dfs עם משתנה חדש, שמועבר באופן רקורסיבי:
האלגוריתם בודק האם יש קודקוד שיש לו 2 ענפים שבכל אחד מהם קיים רכיב
קשירות שמכיל קודקוד מהקבוצה.
אמ"מ קיים קודקוד כזה אז אין מסילה מכוונת.
האם זה נכון? תודה!