#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

#define DIM 5

int matrix [DIM][DIM] = {
	{0,1,0,1,0},
	{1,0,1,0,0},
	{0,1,0,1,0},
	{1,0,1,0,1},
	{0,0,0,1,0},
};

int vater [DIM][DIM];
int markiert [DIM];
int num;

void DFS1 (int knoten)
{
	int i;

	markiert [knoten] = 1;
	for (i=0; i< DIM;i++) {
		if (matrix[knoten][i] == 1)
			if (markiert[i] == 0)
				DFS1 (i);
	}
}


/**findet alle Knoten die von knoten aus
 * erreichbar sind!*/
void finde_erreichbarkeit (int knoten)
{
	int i;
	
	for (i=0; i<DIM;i++) markiert[i] =0;
	DFS1 (knoten);
	printf ("Von Knoten %d sind ", knoten);
	for (i=0; i<DIM;i++) if (markiert[i]) printf ("%d ",i);
	printf ("erreichbar\n");
}

void DFS2 (int knoten)
{
	int i;
	
	markiert [knoten] = num;
	for (i=0; i<DIM;i++)
	{
		if (matrix [knoten][i] && ! markiert[i])
		{
			DFS2 (i);
		}
	}
}

/**Ein ungerichteter Pfad heißt zusammenhängend, wenn
 * für alle u,v gilt: Es existiert ein Pfad von u
 * nach v.*/
void finde_zusammenhang ()
{
	int i;

	for (i=0; i< DIM; i++) markiert[i] =0;
	num=0;
	for (i=0; i<DIM; i++)
	{
		if (! markiert[i])
		{
			num++;
			DFS2 (i);
		}
	}
	printf ("Der Graph enthält %d Komponenten\n", num);
}

void DFS3 (int knoten)
{
	int i;
	
	markiert [knoten] = 1;
	for (i=0; i<DIM;i++) {
		if (matrix[knoten][i]) {
			if (markiert[i] && ! vater [knoten][i]) num++;
			else if (!markiert [i])
			{
				vater [i][knoten] = 1;
				DFS3 (i);
			}
		}
	}
}

/**Sucht nach Kreisen in Graphen.
 * ACHTUNG!!! Gefundene Kreise ist nicht die Anzahl
 * tatsächlich existierender Kreise, wenn es umschließende
 * Kreise gibt.*/
void finde_kreis ()
{
	int i;

	for (i=0; i<DIM;i++) markiert [i] = 0;
	for (i=0; i<DIM*DIM;i++) vater [i/DIM][i%DIM] = 0;
	num = 0;

	for (i=0; i< DIM;i++)
		if (! markiert[i]) DFS3 (i);
	
	if (num) printf ("%d Kreise gefunden\n", num);
	else printf ("Graph ist kreisfrei\n");
}

void DFS4 (int knoten)
{
	int i,max=0,min=INT_MAX;

	markiert [knoten] = -1;	// markiere
	for (i=0; i< DIM;i++) {
		if (matrix[knoten][i] == 1)
			if (markiert[i] == -2)	// nicht markiert
				DFS4 (i);
	}
	// bestimme gruppe
#ifdef DEBUG
	printf ("Knoten %d / Liste:", knoten);
#endif
	for (i=0; i< DIM; i++)
	{
		if (matrix[knoten][i] == 1)	// für alle Nachbarknoten
		{
#ifdef DEBUG
			printf (" %d", markiert [i]);
#endif
			if (markiert [i] < min && 
			markiert [i] >= 0)	// bereits zugewiesen
				min = markiert[i];
			if (markiert [i] > max) max = markiert[i];
		}
	}
#ifdef DEBUG
	printf (" / min: %d, max: %d, \n", min,max);
#endif
	if (min == INT_MAX) markiert [knoten] = 0;	// kein Nachbar
	else if (min>0) markiert[knoten] = min - 1;
	else markiert[knoten] = max + 1;
}

/**Diese Funktion versucht Gruppen für den Graphen zu
 * zu vergeben! Dabei dürfen natürlich keine zwei Gruppen
 * nebeneinander vergeben werden!*/
void gib_gruppen ()
{
	int i;
	
	for (i=0; i<DIM; i++) markiert [i] = -2; 
	DFS4(0);
	for (i=0; i<DIM; i++) 
		printf ("(%d,%c) ", i, markiert [i] + 'A');
	printf ("\n");
}

int DFS5 (int knoten, int farbe)
{
	int i;

	markiert[knoten] = farbe;
	for (i=0; i< DIM; i++)
	{
		if (matrix[knoten][i] == 1)	// Nachbarknoten
		{
			if (markiert [i] == -1)
				if (DFS5(i,!farbe))
					return 1;
			if (markiert[i] == farbe)
				return 1;
		}
	}
	return 0;
}

/**Diese Funktion überprüft, ob der Graph mit 2 Farben
 * färbbar ist, ohne, dass zwei nachbarn die gleiche Farbe
 * bekommen!*/
void zwei_faerbbar ()
{
	int i;
	
	for (i=0; i< DIM; i++)
		markiert [i] = -1;
	if (DFS5 (0,0))
		printf ("Nicht mit zwei Farben einfärbbar!\n");
	else printf ("Kann mit zwei Farben eingefärbt werden!\n");
}

int main()
{
	finde_erreichbarkeit (0);
	finde_zusammenhang ();
	finde_kreis();
	gib_gruppen ();
	zwei_faerbbar();
	return 0;
}