Zadanie polegające na znajdowaniu cyklu i określeniu spójności

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;

}

Kod dla sprawdzania spójności i wykrywania cykli wygląda na oko dobrze.
Tyle że ten trzeci warunek wcale nie wynika z dwóch pierwszych i też go trzeba sprawdzić.
Zauważ że jest tam mowa o istnieniu jednej ścieżki, od której wszystkie wierzchołki będą miały odległość co najwyżej 1, więc bardzo prosto skonstruować graf bez cykli i spójny, który nie spełnia 3:

1
|
2
|
3--4--5
|
6
|
7

neves napisał(a):

Kod dla sprawdzania spójności i wykrywania cykli wygląda na oko dobrze.
Tyle że ten trzeci warunek wcale nie wynika z dwóch pierwszych i też go trzeba sprawdzić.
Zauważ że jest tam mowa o istnieniu jednej ścieżki, od której wszystkie wierzchołki będą miały odległość co najwyżej 1, więc bardzo prosto skonstruować graf bez cykli i spójny, który nie spełnia 3:

1
|
2
|
3--4--5
|
6
|
7

Co znaczy, że jeżeli weźniemy jakiś wierzchołek u i ten wierzchołek ma co najmniej 3 ścieżki do 3 różnych wierzchołków o długości 2, to nie spełni warunku trzeciego. To już powinno pozwolić zmodyfikować DFSa to sprawdzenia warunku trzeciego. Tzn po powrocie z wywołania DFSa zapisujemy sobie lokalnie długości ścieżki które przebył DFS. Jeżeli mamy co najmniej 3 o długości co najmniej 2 lub 2 ścieżki o długości co najmniej 2 i odległość, którą pokonał DFS od wierzchołka startowego (trzeba ją przekazywać do wywołania DFSa) jest większa od jeden to trzeci warunek jest niezpełniony.

Czy pominąłem jakiś przypadek?

-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).

Wszystko zależy co znaczy połączenie. Pojedyncza krawędź, czy ścieżka ? Jeśli ścieżka to Twoje twierdzenie jest prawdziwe, jeśli to jest jedna krawędź to testy, które przechodzisz są słabe. W tym drugim przypadku przyjmij, że zachodzi warunek pierwszy i drugi. Co gdybyś  spróbował uciąć wszystkie węzły stopnia jeden ? Jak powinien wyglądać powstały graf ?

Pewnie macie rację jeśli chodzi o 3 warunek, ale chyba jest coś spartaczone także z cyklami. Bo w wiekszosci przypadków (też nie wszystkich) algorytm wypisuje NIE, zamiast TAK, czyli albo stwierdza niespójność albo obecność cykli

Super, działa! Dzięki wszystkim za pomoc