OJ Board

Code: Select all

[pascal]program n615;
var
  graph : array[1..1000] of array[1..1000] of integer;
  marked : array[1..1000] of array [1..1000] of integer;
  quantity : array[1..1000] of integer;
  bg,nd : integer;
  i,j : integer;
  subgraph : integer;
  max : integer;
  tree : boolean;
  connections : integer;
  head : INTEGER;
  testnr : integer;
procedure dfs(x : integer);
var
  i : integer;
begin
  if marked[subgraph,x] = 1 then
    begin
     tree := false;
     exit;
    end;

  for i:= 1 to max do
    begin
      if odd(graph[x,i]) then dfs(i);
    end;
  marked[subgraph,x] := 1;
  inc(quantity[subgraph]);
end;



begin
 { assign(input,'input.txt');
  assign(output,'output.txt');
  reset(input);
  rewrite(output);
  }read(bg,nd);
  testnr := 1;
while true do
begin

  connections := 0;
  fillchar(quantity,sizeof(quantity),0);
  fillchar(graph,sizeof(graph),0);
  fillchar(marked,sizeof(marked),0);
  max := 0;
  tree := true;
  max := bg;
  head := 0;
  if nd > max then max := nd;
  graph[bg,nd] := 1;
  while bg + nd <> 0 do
    begin
      read(bg,nd);
      graph[bg,nd] := 1;
      if nd > max then max := nd;
      if bg > max then max := bg;
    end;
  for subgraph := 1 to max do
    begin
      dfs(subgraph);
      if not(tree) then break;
    end;
  for i := 1 to max do
    begin
    connections := 0;
    for j := 1 to max do
      begin
        if graph[j,i] = 1 then inc(connections);
        if connections > 1 then
          begin
            tree := false;
            break;
          end;
      end;
      if not(tree) then break;
    end;
  connections := 0;
  for i:= 1 to max do
    if quantity[i] >= connections then
      begin
        connections := quantity[i];
        head := i;
      end;
  for i:= 1 to max do
    if (quantity[i] = connections) and (i<>head)then
      begin
        tree := false;
        exit;
      end;
  for i:= 1 to max do
    begin
      if i = head then continue;
      if (quantity[i] <> 1) and (marked[head,i] <> 1) then
        begin
          tree := false;
          break;
        end;
    end;
  read(bg,nd);
  if not tree then writeln('Case ',testnr, ' is not a tree.')
              else writeln('Case ',testnr, ' is a tree.');
  if bg < 0 then
  begin
    break;
  end;
  inc(testnr);
 { readln;}
end;


end.


[/pascal]

Code: Select all

0 0

Code: Select all

10006 10008 10005 10003  10005 10002 10006 10004
10005 10006  0 0
-1 -1

Code: Select all

1 1
0 0

1 2
1 2
0 0

1 2
2 1
0 0

1 2
3 4
4 3
0 0

-1 -1

Code: Select all

#include <iostream.h>

#define SIZE 1000000

int a[SIZE], d[SIZE];

void main(void)
{
	int i, last, n1, n2, pfound, cfound, istree, noparents, cnt=0;
	while (1){
		last=0;
		istree=1;
		cnt++;
		while (1){
			cin >> n1 >> n2;
			if (n1==0 && n2==0) break;
			if (n1<0 && n2<0)	break;
			if (n1==n2)  istree=0;
			
			if (istree==0)
				continue;

			pfound=0;
			cfound=0;

			for (i=0;i<last && (pfound==0 || cfound==0);i++){
				if (a[i]==n1){
					pfound=1;
				}
				if (a[i]==n2){
					if (d[i]==1){
						istree=0;
						break;
					}
					else{
						d[i]=1;
						cfound=1;
					}
				}
			}

			if (i==last){
				if (!pfound){
					a[last]=n1;
					d[last]=0;
					last++;
				}
				if (!cfound){
					a[last]=n2;
					d[last]=1;
					last++;
				}
			}
		}

		if (n1<0 && n2<0)	break;

		if (istree){
			noparents=0;
			for (i=0;i<last && noparents<=1;i++)
				if(d[i]==0 )	noparents++;
			if (last>0 && noparents!=1)
				istree=0;
		}

		if (istree)
			cout << "Case " << cnt << " is a tree.";
		else
			cout << "Case " << cnt << " is not a tree.";
		cout << endl;
	}
}