4. DAG felismerése

• Amint tanultuk, a mélységi bejárás (DFS) alkalmas annak eldöntésére hogy egy irányított gráf körmentes-e (azaz DAG) a következő állítás miatt. Legyen \(G = (V, E)\) egy irányított gráf. Ekkor \(G\) akkor és csak akkor DAG, ha a mélységi bejárása során nincs visszaél.
• A feladat egy olyan Python program írása, mely a fenti (és a jegyzetben is vázolt) módon DFS segítségével eldönti egy adott összefüggő irányított gráfról, hogy DAG-e. Ehhez először keresni kell egy csúcsot amibe nem futnak be élek. Ha nincs ilyen, akkor a gráf biztos hogy nem körmentes. Ezután az így megtalált gyökérből indítsunk egy mélységi bejárást, és nézzük meg hogy keletkezik-e visszaél.
• A feltöltendő fájl neve dag.py legyen.
• A program a bemenetet parancssori argumentum formájában kapja meg a következő módon:

  python3 dag.py graph.text
  

• Az első argumentum (a példában graph.text) egy összefüggő, irányított egyszerű gráf, amit a következő módon adunk meg egy szöveges (.text) fájlban:
  1. A fájl első sorában az \(N\), \(M\) természetes számok találhatóak szóközökkel elválasztva, ahol
     • a \(G = (V, E)\) egyszerű gráf csúcsainak halmaza \(V = \{0, 1, 2, \ldots, N-1\}\),
     • az élek száma \(\left| E \right| = M\).
  2. A fájl további \(M\) sora rendre \(U_i\), \(V_i\) számpárokat tartalmaz. Egy ilyen számpár megfelel egy \(\{U_i, V_i\} \in E\) irányított élnek. Egy él csak egyszer szerepel a fájlban.
  3. A bemenet feldolgozására javasoljuk a 3. feladat gráf beolvasó függvényének módosítását. Figyeljünk arra, hogy most a fájl első sorában nem szerepelnek az \(S\) és \(T\) csúcsok.
• Amennyiben a gráf DAG, a

  DAG
  

  amennyiben nem, akkor a

  Nem DAG
  

  szöveget írjuk ki a terminálra.

• Próbáljuk ki az elkészült programot a graph1.text (DAG) és graph2.text (nem DAG) bemenetekre, de teszteljük más, saját készítésű teszbemeneteken is!