Ocena użytkownikóww: ***** / 2
Nadesłany przez Tomasz Lubiński, 09 sierpnia 2005 01:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.
graficzny2_c.cpp:
//www.algorytm.org
//algorytm testowania czy podany ciąg stopni wierzcholków grafów jest graficzny
//Tomasz Lubiński (c)2003
#include <stdio.h>
#include <conio.h>
int graficzny;
int n,i,s;
int c[100];
//sortuje ciąg nierosnąco
void sort(int c[100], int n)
{
int j,k;
int flag;
flag=1;
while (flag==1)
{
flag=0;
for (j=0; j<n-1; j++)
if (c[j]<c[j+1])
{
k=c[j];
c[j]=c[j+1];
c[j+1]=k;
flag=1;
}
}
}
main ()
{
//pobierz dane
printf("Podaj liczbe wierzcholkow grafu\n");
scanf("%d",&n);
for (i=0; i<n; i++)
{
printf("Podaj stopien wierzcholka %d\n",i+1);
scanf("%d",&c[i]);
}
//algorytm testowania czy podany ciąg stopni wierzcholkow jest graficzny
graficzny=1;
//sprawdz czy suma ciągu jest liczbą parzystą
s=0;
for (i=0; i<n; i++) s+=c[i];
if ((s%2)!=0) graficzny=0;
else sort(c,n); //posortuj ciąg nierosnąco jeżeli suma jest liczbą parzystą
while ((c[0]!=0) && (graficzny==1))
{
s=0;
for (i=1; i<n; i++)
if (c[i]!=0) s++;
if (c[0]>s) graficzny=0;
else for (i=1; i<=c[0]; i++) c[i]--;
c[0]=0;
sort(c,n);
}
//podaj użytkownikowi wynik
if (graficzny==1) printf("Podany ciąg jest graficzny\n");
else printf("Podany ciąg nie jest graficzny\n");
getch();
}