OJ Board

Posted: **Tue Sep 06, 2005 7:27 pm**

hey everybody ,
i wanted to know something from u people ............
1) given two dfs sequence how to find out if it is represting the same graph.........

2) can some one please mention all the steps of a min cost matching algorithm .........better of to , ford fulkerson method ( the one with bellmanford for finding the augmented path instead of BFS as in maxm flow ) . i know hungerian method is difficult and also hard to code .......

regards

Posted: **Tue Sep 13, 2005 12:52 pm**

I'm sure I already read something about min cost matching on this forum, try searching

Posted: **Tue Sep 13, 2005 3:05 pm**

1) given two dfs sequence how to find out if it is represting the same graph.

Even the same dfs sequence can describe several different graphs,
for example 1 2 3 4 5 equally well describes

Code: Select all

    1             1
   / \           / \
  2   5   and   2   3    and  1-2-3-4-5
 / \               / \
3   4             4   5

In fact the answer to your problem is always yes -- two sequences of length n can represent the complete graph with n vertices.

Posted: **Sat Sep 17, 2005 12:16 pm**

hi everybody ,
the thing i was trying to tell about dfs sequence was vague in my earlier post ......so i better go with an example .....the following problem is from icpc regional [ dhaka site 2004 ] ...can some one point out any particular way to solve this problem ....................as far as i know this is about dfs sequence ...........if i am making any mistakes pliz tell me
http://acmicpc-live-archive.uva.es/nuev ... php?p=3019

thanx in advance

OJ Board

dfs sequence

dfs sequence

sorry for a vague post