ZADATAK 2 - BORNA - 50 bodova

TEST PODACI (skraćeni prikaz)


	Broj 		Broj 
        trafostanica	dalekovoda	Rješenje	Broj bodova
Test 1	2		1		0		2
Test 2	3		2		1		3
Test 3	10		19		2		4
Test 4	20		65		3		5
Test 5	40		168		5		6
Test 6	60		224		10		8
Test 7	80		208		20		10
Test 8	100		287		30		12

OPIS ALGORITMA

Naš zadatak je pronaći točke prekida (articulation points). Algoritam 
koji ćemo koristiti je proširenje DFS-a (depth first search, obilazak 
grafa u dubinu). Vrh x nije točka prekida ako svako dijete y ima neki
 vrh niže u stablu spojen s vrhom višim od x. Ovo je u redu za sve vrhove
 osim za korijen stabla (misli se na stablo koje nastaje DFS-om) jer ne 
postoje vrhovi iznad njega. Korijen je točka prekida ako ima dvoje ili 
više djece, jer jedini put između njegove djece ide preko njega. I sad 
se to jednostavno uklopi u DFS algoritam.

BORNA.PAS

program borna;
const
  MAX_VRHOVA = 100;
var
  f : text;
  broj_vrhova,broj_bridova : integer;
  matrica : array [1..MAX_VRHOVA,1..MAX_VRHOVA] of boolean;

procedure ucitaj;
var
  i,j,x,y : integer;

begin
  assign(f,'BORNA.DAT');
  reset(f);
  readln(f,broj_vrhova,broj_bridova);

  for i := 1 to broj_vrhova do
    for j := 1 to broj_vrhova do
      matrica[i,j] := false;

  for i := 1 to broj_bridova do
    begin
      readln(f,x,y);
      matrica[x,y] := true;
      matrica[y,x] := true;
    end;

  close(f);
end;

procedure rijesi;
var
  i,broj_apova,id : integer;
  polje : array [1..MAX_VRHOVA] of integer;
  ap : array [1..MAX_VRHOVA] of boolean;
  prvi : boolean;

function visit (vrh : integer) : integer;
var
  i,m,min : integer;
  jedan : boolean;

begin
  inc(id);
  polje[vrh] := id;

  min := id;
  jedan := false;

  for i := 1 to broj_vrhova do
    if matrica[vrh,i] then
      if polje[i] = 0 then
        begin
          if (vrh = 1) and jedan then
            prvi := true;
          m := visit(i);
          if m < min then
            min := m;
          if m >= polje[vrh] then
            ap[vrh] := true;
          jedan := true;
        end
      else
        if polje[i] < min then
          min := polje[i];

  visit := min;
end;

begin
  broj_apova := 0;
  id := 0;

  for i := 1 to broj_vrhova do
    begin
      polje[i] := 0;
      ap[i] := false;
    end;

  prvi := false;

  visit(1);

  ap[1] := prvi;

  assign(f,'BORNA.OUT');
  rewrite(f);

  for i := 1 to broj_vrhova do
    if ap[i] then
      inc(broj_apova);

  writeln(f,broj_apova);

  for i := 1 to broj_vrhova do
    if ap[i] then
      writeln(f,i);

  close(f);
end;

begin
  ucitaj;
  rijesi;
end.

BORNA.C

#include <stdio.h>

#define MAX_VRHOVA 100

char matrica[MAX_VRHOVA][MAX_VRHOVA];
int broj_vrhova,broj_bridova,id = 0;

int polje[MAX_VRHOVA],ap[MAX_VRHOVA],prvi;

FILE *fp;

void ucitaj(void)
{
  int i,j;
  int x,y;

  fp = fopen("BORNA.DAT","rt");

  fscanf(fp,"%d\n%d\n",&broj_vrhova,&broj_bridova);

  for (i = 0;i < broj_vrhova;++i)
    for (j = 0;j < broj_vrhova;++j)
      matrica[i][j] = 0;

  for (i = 0;i < broj_bridova;++i)
  {
    fscanf(fp,"%d %d\n",&x,&y);
    matrica[x - 1][y - 1] = matrica[y - 1][x - 1] = 1;
  }

  fclose(fp);
}

int visit(int vrh)
{
  int i;
  int m,min;
  int jedan;

  polje[vrh] = ++id;
  min = id;
  jedan = 0;

  for (i = 0;i < broj_vrhova;++i)
    if (matrica[vrh][i])
      if (!polje[i])
      {
        if (!vrh && jedan)
          prvi = 1;
        m = visit(i);
        if (m < min)
          min = m;
        if (m >= polje[vrh])
          ap[vrh] = 1;
        jedan = 1;
      }
      else
        if (polje[i] < min)
          min = polje[i];

  return min;
}

void rijesi(void)
{
  int i;
  int broj_apova = 0;

  for (i = 0;i < broj_vrhova;++i)
    ap[i] = polje[i] = 0;
  prvi = 0;

  visit(0);

  ap[0] = prvi;

  fp = fopen("BORNA.OUT","wt");

  for (i = 0;i < broj_vrhova;++i)
    if (ap[i])
      ++broj_apova;

  fprintf(fp,"%d\n",broj_apova);

  for (i = 0;i < broj_vrhova;++i)
    if (ap[i])
      fprintf(fp,"%d\n",i + 1);

  fclose(fp);
}

int main(void)
{
  ucitaj();
  rijesi();

  return 0;
}