2 shunfurh shunfurh 于 2017.11.19 19:42 提问

DFS spanning tree 10C

Problem Description
Consider a Depth-First-Search(DFS) spanning tree T of a undirected connected graph G, we define a T-Simple Circle as a path v1, v2, ..., vk (v1 = vk) in G that contains at most one edge which not belongs to the DFS spanning tree T.
Given a graph G, we process DFS on G starting from vertex 1 and get a DFS spanning tree T, then you should choose some edges of G so that all T-Simple Circles contains at least one edge that you choose.
Please minimize the number of edges you choose.

Input
There are at most 100 test cases.
For each case, the first line contains two integers n and m denoting the number of vertices and edges. The vertexes are numbered from 1 to n.
The following m lines describe the graph. Each line contains two integers xi and yi, denoting an edge between vertex xi and yi(xi ≠ yi).
Note that the first n-1 edges of input construct a DFS spanning tree T which is generated by DFS from vertex 1.
Input ends with n = 0 and m = 0
(1 <= n <= 2000, 1 <= m <= 20000, 1 <= xi, yi <= n)

Output
For each case, output the number of minimal edges that you choose.

Sample Input
4 5
1 2
4 2
3 2
1 3
4 1
10 14
1 2
2 9
1 3
3 4
4 10
3 5
5 7
5 8
3 6
9 1
1 10
1 6
7 3
8 3
0 0

Sample Output
1
3

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!