Trees

Given: an undirected graph.
How many edges must you remove to make it a tree? (or a forest of trees?)

Input

As usual.
N ≤ 1000.

Output

The minimum number of edges you have to remove.

Sample Input

3
0 1 1
1 0 1
1 1 0

Sample Output

1

All Submissions
Best Solutions


Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Jun 28, 2013

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Xue_Alex on Jul 15, 2017 - 3:15:22 am UTC Clarification
  • (0/0)
The question states that there can be a forest of trees, does that mean a node with no indegrees and outdegrees counts as a tree in itself, because it still has the properties of a tree (n-1 edges, no cycle, all points strongly connected)

MuhammadKhattak on Dec 15, 2013 - 7:23:26 pm UTC Clarification
  • (5/1)
Would this:
http://imgur.com/gBmIAi4
be an accurate explanation for the input/ output, assuming a blank is a wildcard or am I completely lost? The problem is pretty vague so I need a bit of clarification.

ImbaCalvin on Dec 16, 2013 - 12:33:48 am UTC Re: Clarification
  • (5/0)
You are lost...

MuhammadKhattak on Dec 16, 2013 - 3:32:58 am UTC Re: Clarification
  • (3/0)
Okay, I know it was simplistic though I figured I should try the most simple thing first. I tried googling it again and it seems to be much more complicated, thanks for telling me though.

B on Dec 16, 2013 - 4:38:02 pm UTC Re: Clarification
  • (21/0)
u wot m8