ZADATAK 1 - LJUDI - 50 bodova

TEST PODACI (skraćeni prikaz)


	Broj ljudi	Broj parova	Rješenje	Broj bodova
Test 1	100		70		55, 35		3
Test 2	250		200		162, 66		3
Test 3	500		300		177, 205	5
Test 4	500		700		459, 36		6
Test 5	1000		700		530, 323	6
Test 6	1000		2500		994, 7		7
Test 7	1000		10000		372, 3		10
Test 8	2500		12000		1387, 104	10

OPIS ALGORITMA

Na početku se kreiraju vezane liste za svakog čovjeka posebno, 
a zatim kako se obrađuju informacije o poznanstvima, one se spajaju 
u veće liste ljudi koji se međusobno poznaju. Na kraju je dovoljno
 prebrojiti koliko je ostalo takvih listi (to je maksimalni broj ljudi 
koji se međusobno ne poznaju), te pronaći najveću listu i prebrojiti 
njene članove (to je maksimalni broj ljudi koji se medjusobno poznaju).

LJUDI.PAS

Program ljudi;

Const
        maks = 2500;
        indata = 'LJUDI.DAT';
        space = ' ';

Type
        mojstring = String[20];
        niz_ljudi = Array[1..maks] Of mojstring;

Var
        f : Text;
        ljudi : niz_ljudi;
        poznaje : Array[1..maks] Of Integer;
        aux : Array[1..maks] Of Integer;
        foo, line : String;
        broj_ljudi : Integer;

{ ------------------------------------------------------------------- }

Procedure quicksort(l,r : Integer);
Var
          x    : mojstring;
          i, j : Integer;

Begin
   i := l;
   j := r;
   x := ljudi[(l+r) DIV 2];
   Repeat
     While ljudi[i] < x Do i := i + 1;
     While x < ljudi[j] Do j := j - 1;
     If i <= j Then Begin
       foo := ljudi[i];
       ljudi[i] := ljudi[j];
       ljudi[j] := foo;
       i := i + 1;
       j := j - 1;
     End;
   Until i>j;

   If l < j Then quicksort(l,j);
   If i < r Then quicksort(i,r);

End;

{ ------------------------------------------------------------------- }

Procedure binfind(Var covjek : mojstring; Var ind : Integer);

Var
        i, j, k : Integer;
Begin

  ind := 0;
  i := 1;
  j := broj_ljudi;
  While (ind = 0) AND (i <= j) Do Begin
    k := (i+j) DIV 2;
    If covjek = ljudi[k]
    Then ind := k
    Else If covjek < ljudi[k]
         Then j := k-1
         Else i := k+1;
  End;

End;

{ ------------------------------------------------------------------- }

Procedure initialize;

Var
        i : Integer;

Begin

  Assign(f,indata);
  Reset(f);
  Readln(f,broj_ljudi);
  For i := 1 To broj_ljudi Do Begin
    Readln(f,ljudi[i]);
    poznaje[i] := i;
    aux[i] := 1;
  End;

End;

{ ------------------------------------------------------------------- }

Procedure upoznavanje;

Var
        prvi, drugi : mojstring;
        i, broj_parova, foo, iprvi, idrugi : Integer;
        p : Byte;

Begin

  Readln(f,broj_parova);

  For i := 1 To broj_parova Do Begin

    Readln(f,line);

    p := Pos(space,line);
    prvi := Copy(line,1,p-1);
    Delete(line,1,p);
    drugi := line;
    binfind(prvi,iprvi);
    binfind(drugi,idrugi);

    If poznaje[iprvi] <> poznaje[idrugi] Then Begin

      While iprvi <> poznaje[iprvi] Do iprvi := poznaje[iprvi];
      While idrugi <> poznaje[idrugi] Do idrugi := poznaje[idrugi];
      If iprvi > idrugi Then Begin
        foo := iprvi;
        iprvi := idrugi;
        idrugi := foo;
      End;

      poznaje[idrugi] := iprvi;

    End;
    
  End;

  Close(f);

End;

{ ------------------------------------------------------------------- }

Procedure pripremi;

Var
        foo, zadnji : Integer;

Begin

  zadnji := broj_ljudi;

  While zadnji > 1 Do Begin

    foo := zadnji;
    While foo <> poznaje[foo] Do Begin
      Inc(aux[poznaje[foo]],aux[foo]);
      aux[foo] := 0;
      foo := poznaje[foo];
    End;

    Repeat
      Dec(zadnji);
    Until aux[zadnji] <> 0;

  End;

End;

{ ------------------------------------------------------------------- }

Procedure zavrsi;

Var
        i, najgrupa, najantigrupa : Integer;

Begin

  najgrupa := 0;
  najantigrupa := 0;
  For i := 1 To broj_ljudi Do
    If aux[i] > 0 Then Begin
      Inc(najantigrupa);
      If aux[i] > najgrupa Then najgrupa := aux[i];
    End;

  Writeln;
  Write('Broj clanova u najvecoj grupi medjusobnih poznanika : ');
  Writeln(najgrupa);
  Write('Broj clanova u najvecoj grupi medjusobnih nepoznanika : ');
  Writeln(najantigrupa);

End;

{ ------------------------------------------------------------------- }
{ ------------------------------------------------------------------- }

Begin

  initialize;
  quicksort(1,broj_ljudi);
  upoznavanje;
  pripremi;
  zavrsi;

End.

LJUDI.C

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

struct covjek {
                char ime[25];
                struct covjek *poznanik;
              };
typedef struct covjek covjek;

covjek *ljudi[2500];
int broj_ljudi , broj_parova;

void test ( char *s )
{
  int i , broj = 0;
  covjek *trenutni;

  for( i=0,trenutni=ljudi[i] ; i<broj_ljudi ; ++i,trenutni=ljudi[i] )
     while( trenutni != NULL )
      {
        ++broj;
        trenutni = (*trenutni).poznanik;
      }
  printf( "%d %s" , broj , s );
}

covjek *KrajGrupe( char *ime , covjek **pocetni )
{
 int i , j;
 covjek *trenutni , *prvi ;

 for( j=0 , prvi=trenutni=ljudi[j] ; j<broj_ljudi ; ++j , prvi=trenutni=ljudi[j] )
    while( trenutni != NULL )
      {
        i=0;
        while( ime[i]==(*trenutni).ime[i] )
          {
            if( ime[i] == '\n' )
              {
               while( (*trenutni).poznanik != NULL )
                      trenutni = (*trenutni).poznanik;
               *pocetni = prvi;
               return trenutni;
              }
            ++i;
          }
        trenutni = (*trenutni).poznanik;
      }

 return NULL;
}

covjek *PocetakGrupe( char *ime , covjek *provjera )
{
 int i , j;
 covjek *trenutni , *pocetak;

 for( j=0 , pocetak=trenutni=ljudi[j] ; j<broj_ljudi ; ++j , pocetak=trenutni=ljudi[j] )
    while( trenutni != NULL )
      {
        i=0;
        while( ime[i]==(*trenutni).ime[i] )
        {
         if( ime[i] == '\n' )
           {
             if( provjera != pocetak )
                 ljudi[j]=NULL;
             return pocetak;
           }
         ++i;
        }
        trenutni = (*trenutni).poznanik;
      }

 return NULL;
}

void main ( void )
{
  FILE *in;
  covjek *zadnji , *prvi , *trenutni , *provjera;
  int i , j;
  char par[50] , *drugi;
  int maxpoz , maxnepoz , tmp;

  in = fopen( "LJUDI.DAT" , "r" );

  fscanf( in , "%d\n" , &broj_ljudi );

  for( i=0 ; i<broj_ljudi ; ++i )
  {
    ljudi[i] = malloc( sizeof(covjek) );
    (*ljudi[i]).poznanik = NULL;
    fgets( (*ljudi[i]).ime , 25 , in );
  }

  fscanf( in , "%d\n" , &broj_parova );

  for( i=0 ; i<broj_parova ; ++i )
  {
    fgets( par , 50 , in );
    j=0;
    while( par[j]!=' ' ) ++j;
    par[j]='\n';
    if( (par[0]=='I') && (par[1]=='v') && (par[2]=='i') &&
        (par[3]=='c') && (par[4]=='a') && (par[5]=='1') )
            printf("");
    drugi = par+j+1;

    zadnji = KrajGrupe( par , &provjera );
    prvi = PocetakGrupe( drugi , provjera );
    if( provjera != prvi )
      (*zadnji).poznanik = prvi;
  }

  fclose( in );

  maxpoz = 0;
  maxnepoz = 0;

  for( j=0 , trenutni=ljudi[j] ; j<broj_ljudi ; ++j , trenutni=ljudi[j] )
   if( trenutni != NULL )
   {
     ++maxnepoz;
     tmp=0;
     while( trenutni != NULL )
     {
       ++tmp;
       trenutni = (*trenutni).poznanik;
     }
     if( tmp > maxpoz )
       maxpoz = tmp;
   }

  printf( "Broj clanova u najvecoj grupi medjusobnih poznanika : %d\n" , maxpoz );
  printf( "Broj clanova u najvecoj grupi medjusobnih nepoznanika : %d\n" , maxnepoz );
}