Liczba trójkątów w grafie

0

Jak możnaby sprawdzić ww liczbę? O ile wiem mniejwięcej co z resztą (stopień min/max, liczba składowych spójności), to akurat na to, nie mam pomysłu :(.

0

podnieść macierz przyległości do 3 potęgi, zsumować wartości na głównej przekątnej i podzielić przez 6

0

Hm, nie bardzo Cię zrozumiałem, spróbowałem wykombinować coś po swojemu mając do dyspozycji macierz sąsiedztwa:

 
int trojakty(int **macierz, int size)
{
	int wynik = 0;
	for(int i = 0; i < size - 1; i++) //wiersze
	{
		//kolumny
		for(int n = 0; n < size - 1; n++)
		{
			if(macierz[i][n] != 0 && macierz[i][n+1] != 0 && macierz[i+1][n+1] != 0) //jeżeli mam taką trójkę
			{
				wynik += (macierz[i][n] * macierz[i][n+1] * macierz[i+1][n+1]);
				macierz[i][n] = 0; //zeruję pola jak i ich symetryczne odpowiedniki
				macierz[n][i] = 0;
				macierz[i][n+1] = 0;
				macierz[n+1][i] = 0;
				macierz[i+1][n+1] = 0;
				macierz[n+1][i+1] = 0;
			}
		}
	}
	return wynik;
}

Jednak ten sposób nie działa (chyba?) do końca poprawnie, przechodzi tylko 2/6 testów (SPOJ - contest zamknięty, przykro mi). Jakieś dalsze wskazówki? Co pomijam w powyższym rozwiązaniu, jaki przypadek?

0

Twój algorytm nie rozumiem za bardzo...

macierz przyległości/sąsiedztwa zawiera liczbę tras długości jeden pomiędzy poszczególnymi wierzchołkami
po podniesieniu jej do trzeciej potęgi otrzymujemy w macierzy trasy długości 3
interesują nas trójkąty, czyli trasy zaczynające się i kończące w tym samym miejscu, więc sumujemy trasy z głównej przekątnej
każdy trójkąt został policzony w 3 wierzchołkach oraz przechodząc po nim w dwóch kierunkach, więc dzielimy na 6
ten opis zakłada, że graf jest nieskierowany i nie ma pętli, jeśli tak nie jest, trzeba go zmodyfikować odrobinę

1 użytkowników online, w tym zalogowanych: 0, gości: 1