2015
09-17

# DFS spanning tree

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.

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)

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)

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

1
3
Hint
Here is the graph G in the first test case:

The solid lines denote the edge which belongs to the DFS spanning tree, and the dotted lines denote the others.
For first case, we can choose one edge (1, 2)
For second case, we can choose three edges (1, 2), (1, 3), (3, 5)


#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <queue>
#include <stack>
#include <utility>
#include <set>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define N 2005
int n , m , pre[N] , mcnt , f[N] , dep[N];
struct edge
{
int x , f , next;
}e[40005];
pair<int , int> a[20005];
bool vis[N];
void dfs(int x , int fa)
{
f[x] = fa , dep[x] = dep[fa] + 1 , vis[x] = 1;
for (int i = pre[x] ; ~i ;i = e[i].next)
if (!vis[e[i].x])
e[i].f = e[i ^ 1].f = 1 , dfs(e[i].x , x);
}

bool cmp(pair<int , int> x, pair<int , int> y)
{
if (dep[x.se] == dep[y.se])
return dep[x.fi] > dep[y.fi];
return dep[x.se] > dep[y.se];
}

void work()
{
int i , j , x , y , ans = 0;

memset(pre , -1 , sizeof(pre));
mcnt = 0;
for (i = 1 ; i <= m ; ++ i)
{
scanf("%d%d",&x,&y);
a[i] = make_pair(x , y);
}
for (i = m ; i > 0 ; -- i)
{
x = a[i].fi , y = a[i].se;
e[mcnt] = (edge) {y , 0 , pre[x]} , pre[x] = mcnt ++;
e[mcnt] = (edge) {x , 0 , pre[y]} , pre[y] = mcnt ++;
}
memset(vis , 0 , sizeof(vis));
dfs(1 , 0);
m = 0;
for (x = 1 ; x <= n ; ++ x)
for (i = pre[x] ; ~i ; i = e[i].next)
if ((i & 1) && !e[i].f)
{
y = e[i].x;
a[++ m] = make_pair(x , y);
if (dep[a[m].fi] < dep[a[m].se])
swap(a[m].fi , a[m].se);
}
sort(a + 1 , a + m + 1 , cmp);
memset(vis , 0 , sizeof(vis));
for (i = 1 ; i <= m ; ++ i)
{
x = a[i].fi , y = a[i].se;
//cout << x <<' '<< y << endl;
while (f[x] != y)
if (vis[x])
break;
else x = f[x];
if (!vis[x])
vis[x] = 1 , ++ ans;
}
printf("%d\n" , ans);
}

int main()
{
while (scanf("%d%d",&n,&m) , n || m)
work();
return 0;
}