I got WA#2 too,
but I thought that the graph is supposed to be not connected.

Can help me identify my errors , here's my solution :
- I reverse all the edges
- DFS from the vertex without any other vertex pointing to
- Count the depth, if depth = number of vertex -> output in reverse order

3Q,i made the same mistake,and i now get AC

One of the lines in test 4 has trailing space. This old problem was designed for Pascal/C++, such inputs treated as a bad style nowadays.

It is an algorithm with complexity O(N^3) to find shortest distance between all vertices of a graph.

http://en.wikipedia.org/wiki/Topological_sorting
http://algolist.manual.ru/sort/top_sort.php (in russian)
...
...

Google forever!

Your example isn't correct.
"At least one such sequence always exists."

System gives WA#1 me too.
____
Sorry for my English.

Edited by author 29.01.2010 23:40

chunki 3 5ni farzandi

Edited by author 08.07.2011 16:39

Because 5 is parent of 3

You tried to solve problem 1022 Genealogical tree.
Your solution was compiled with the following errors:

8421e763-05ba-4aea-b470-f7f9a3d55a5e(16,5) Error: Illegal assignment to for-loop variable "j"
8421e763-05ba-4aea-b470-f7f9a3d55a5e(39,4) Fatal: There were 1 errors compiling module, stopping
8421e763-05ba-4aea-b470-f7f9a3d55a5e(39,4) Fatal: Compilation aborted


You cannot modify iterator in for-loop directly, replace

for j:=1 to 2 do
begin
if 1=2 then j := 3;
end;

with

j := 1;
while j <= 2 do
begin
if 1=2 then j := 3;
inc(j);
end;

And don't use unit crt, read FAQ about how to do input/output.

2170208 13:57:22 23 июл 2008 Mansurov Artur 1022 C++ Accepted 0.001 153 КБ

O(n^2) simple search

program Mars;

uses
  SysUtils;

type
  TPNext = ^ElemIO;
  ElemIO = record
    Vert: byte;
    Next: TPNext;
  end;

var
  Numbers, Parents: array [1..100] of byte;
  Point: array [1..100, 0..100] of byte;
  Beg, En: TPNext;
  Num, N, w, a, q: Byte;
  NewV: array [1..100] of boolean;
  f: Text;

procedure Push(v: byte);
var ne: TPNext;
begin
  New(ne);
  if Beg = nil then Beg:= Ne;
  Ne^.Vert:= V;
  Ne^.Next:= nil;
  if En = nil then En:= ne
  else begin
    En^.Next:= Ne;
    En:= Ne;
  end;
end;

function Pop: byte;
var ne:TPNext;
begin
  result:= Beg^.Vert;
  Ne:= Beg;
  Beg:= Ne^.Next;
  if Beg = nil then En:= nil;
  Dispose(Ne);
end;

Procedure OW(v: byte);
var i, p: byte;
begin
  Push(v);
  while Beg <> nil do begin
    p:= Pop;
    Numbers[Num]:= p;
    inc(num);
    for I := 1 to Point[p, 0] do
      if NewV[Point[p, i]] then begin
        Push(Point[p, i]);
        NewV[Point[p, i]]:= false;
      end;
  end;
end;

procedure GetTheOldest;
var
  i, q: byte;
begin
  FillChar(Parents, N, 0);
  for i := 1 to N do
    for q := 1 to Point[i, 0] do
      inc(Parents[Point[i, q]]);
  Num:=1;
  for I := 1 to N do
    if Parents[i] = 0 then begin
      OW(i);
      NewV[i]:= false;
    end;
end;

begin
  for w := 1 to 100 do
    for a := 0 to 100 do
      Point[w, a]:= 0;

  AssignFile(f, 'input.txt');
  reset(f);
  N:=0;
  read(f, N);
  for w := 1 to N do
  begin
    read(f, a);
    q:= 1;
    while a <> 0 do begin
      Point[w, q]:= a;
      inc(Point[w, 0]);
      Read(f, a);
      inc(q);
    end;
  end;
  CloseFile(f);


  FillChar(NewV, N, True);
  Beg:= nil;
  En:= nil;
  GetTheOldest;

  For w:=1 to N do
    If NewV[w] then OW(w);
  AssignFile(f, 'output.txt');
  rewrite(f);
  if n <> 0 then
    for w := 1 to N do
      if w = N then write(f, Numbers[w])
      else write(f, Numbers[w], ' ');
  CloseFile(f);
end.

when you submit code
you can set option
"Reply" in "To this E-Mail address"

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main()
{
    int i, k, n;
    cin >> n;
    vector< set<int> > out(n), in(n);
    for (i=0;i<n;i++) while (cin>>k, k) { out[i].insert(--k); in[k].insert(i); }
    set<int> q;
    for (i=0;i<n;i++) if (in[i].empty()) q.insert(i);
    vector<int> top;
    while (!q.empty()) {
        top.push_back(k=*q.begin());
        q.erase(q.begin());
        for (set<int>::iterator it=out[k].begin();it!=out[k].end();++it) {
            i=*it;
            in[i].erase(k);
            if (in[i].empty()) q.insert(i);
        }
    }
    cout << top[0]+1; for (i=1;i<n;i++) cout << ' ' << top[i]+1;
    return 0;
}