Witam. Jest zadanie, w którym trzeba wczytać k grafów i odpowiedzieć na pytanie TAK lub nie NIE, w zależności czy graf spełnia 3 warunki:
-pomiędzy dowolną parą wierzchołków istnieje ścieżka
-w grafie nie ma cykli
-w grafie istnieje pewna ścieżka, taka, że każdy wierzchołek grafu znajduje się na tej ścieżce lub jest sąsiadem ścieżki (istnieje połączenie między danym wierzchołkiem a dowolnym wierzchołkiem na ścieżce).
Wydaje mi się, że jeżeli warunek 1 i 2 będzie spełniony to siłą rzeczy także i 3. Mam rację?
Napisałem kod, który niby działa na testach wstępnych, próbowałem wymyślić jakieś przkłady, ale zawsze pokazuje dobrze. Mam jednakże wrażenie, że moje określanie cykliczności jest jakieś wadliwe (bo żeby określić spójność to sprawdzam, czy wszystkie wierzchołki zostały odwiedzone). Co zrobiłem źle?
#include <iostream>
#include <vector>
#include <algorithm>
using namespace::std;
vector<long long> t [100005];
bool odwiedzony[100005];
long long n, m, k, a, b = 0;
bool cykle = false;
bool spojny = true;
long long poprzedni = -1;
vector <bool> wyniki;
void DFS(long long start)
{
odwiedzony[start] = true;
for(long long i = 0; i < t[start].size(); i++)
if(!odwiedzony[t[start][i]])
{
poprzedni = start;
DFS(t[start][i]);
} else if(t[start][i] != poprzedni && poprzedni != start && t[start][i] != start)
{
//cout << t[start][i] << " " << poprzedni << " obecny: " << start << endl;
cykle = true;
}
}
int main()
{
ios_base::sync_with_stdio (false);
cin >> k;
for(long long j = 0; j < k; j++)
{
cin >> n >> m;
for(long long i = 0; i < m; i++)
{
cin >> a >> b;
t[a].push_back(b);
t[b].push_back(a);
}
DFS(1);
//cout << cykle << " ";
for(long long i = 1; i <= n; i++)
{
t[i].clear();
if(!odwiedzony[i])
spojny = false;
else
odwiedzony[i]=false;
}
//cout << cykle << " " << spojny << endl;
if(!cykle && spojny)
wyniki.push_back(true);
else
wyniki.push_back(false);
poprzedni = -1;
cykle = false;
spojny = true;
}
for(long long i = 0; i < k; i++)
if(wyniki[i])
cout << "TAK" << endl;
else
cout << "NIE" << endl;
}