Potrzebuję program który by wyszukiwał cykl w grafach skierowanych.
Ma on wczytać:
"n" liczbę wierzchołków w grafie,
"m" liczbę krawędzi w grafie,
m par liczb "a" oraz "b" reprezentujących skierowane krawędzie z wierzchołka a do b, wierzchołki będą numerowane liczbami od 0 do n-1 włącznie.
A następnie program powinien wypisać jako wynik „TAK”, zawiera cykl, lub „NIE” w przeciwnym wypadku.
Zacząłem już program tylko nie wiem za bardzo co wpisać do main... (o krawedzie chodzi):
#include <string>
#include <vector>
#include <iostream.h>
using namespace std;
const int maxn= 100;
bool v[maxn]; // stan odwiedzenia wierzchołków
int currentTime; // aktualna wartość etykiety czasowej
int czas[maxn]; // czasy przetworzenia poszczególnych wierzchołków
vector<int> g[maxn]; // listy następników
int n; // liczba wierzchołków
int m; // liczba krawędzi
void dfsDGo(int start) {
for (vector<int>::iterator it = g[start].begin(); it != g[start].end(); ++it)
if(!v[*it]) {
v[*it] = true;
dfsDGo(*it);
}
czas[start] = ++currentTime;
}
bool dfsD() {
// na początku żaden wierzchołek nie został odwiedzony
for (int i = 0; i < n; ++i)
v[i] = false;
// ustalamy początkowy czas na 0
int currentTime= 0;
// uruchamiamy przeszukiwanie z każdego wierzchołka
for (int i = 0; i < n; ++i)
if(!v[i]) {
v[i] = true;
dfsDGo(i);
}
// weryfikujemy otrzymane czasy przetworzenia:
for (int i = 0; i < n; ++i)
for (vector<int>::iterator it = g[i].begin(); it != g[i].end(); ++it)
if(czas[i] <= czas[*it])
// jeśli dla jakiejś krawędzi u -> v nie zachodzi time[u] > time[v], oznacza to, że // znalezione uporządkowanie jest niepoprawne, a więc w grafie jest cykl
return true;
// jeśli opisywany warunek jest spełniony dla wszystkich krawędzi,
// graf jest acykliczny
return false;
}
int main()
{
cin>>n;
cin>>m;
// tu trzeba jakos wpisac krawedzie tylko nie wiem jak... ;/
bool wynik = dfsD();
cout<<wynik;
// potem przerobyc jesli true to tak, a jak false to nie.. to juz nie problem
return 0;
}
MATERIAŁY DO TEGO ZADANIA:
http://www.lo8.poznan.pl/portal/documents/attachments/ATTACH4ad5ffceb9d9f.pdf
Z góry dzięki za pomoc.