Nezavisla mnozina grafu

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

int** graf = NULL; //matica susednosti
int* independent_set = NULL; //nezavisla mnozina vrcholov
int n; //pocet vrcholov
int in_count;

int main(void)
{
	printf("zadajte pocet vrcholov grafu: ");
	scanf("%d",&n);
	
	graf= (int**)calloc(n,1+sizeof(int*));
	for(int i=0;i<n;i++) 
		graf[i] = (int*) calloc(n,sizeof(int));
	
	for(int i = 0; i<n; i++) {
        for(int j = 0;j<n;j++) {
            graf[i][j] = 0;
        }
		printf("\n");
    }
	
	char k;
	printf("Pre ukoncenie zadavania pre konkretny vrchol zadajte znak k \n");
	
	for(int i=0; i<n; i++){
		printf("zadajte susedov vrcholu %d: \n",i);
		k = NULL;
		while(1){
			fflush(stdin);
			k = getchar();
			if(k == 'k'){
				break;
			}
			else{
				graf[i][atoi(&k)] = 1;
				graf[atoi(&k)][i] = 1;
			}
		}
	}
	
	printf("Zadajte pocet vrcholov mnoziny, ktoru chcete overit:\n");
	scanf("%d",&in_count);
	
	independent_set = (int*) malloc(in_count*sizeof(int));
	printf("Zadajte jednotlive vrcholy: \n");
	for(int i=0; i<in_count; i++){
		fflush(stdin);
		k = getchar();
		independent_set[i] = atoi(&k);	
	}
	int independent = 1; //priznak 
	for(int i=0; i<in_count; i++){
		for(int j=0; j< in_count; j++){
			if(i==j) continue;//vrchol nemoze susedit sam so sebou
			if(graf[independent_set[i]][independent_set[j]] == 1){//nasli sme dva susediace vrcholy
				independent = 0;
			}
		}
	}

	
	printf("Graf: \n");
	
	for(int i = 0; i<n; i++) {
		for(int j = 0;j<n;j++) {
			printf("%d ",graf[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	printf("Mnozina: \n");
	
	for(int i=0; i<in_count; i++){
		printf("%d",independent_set[i]);	
	}
	printf("\n");

	if(independent)
		printf("Tvori nezavislu mnozinu v grafe\n");
	else
		printf("Netvori nezavislu mnozinu v grafe\n");

	system("pause");
	return 0;
}

Informácie:

Autor: danciwo
www: http://www.danciwo.net
Kategória: Algoritmy
Jazyk: C/C++
Dátum:12/15/2009 5:11:51 PM