首页 > 搜索 > DFS搜索 > HDU 4582-DFS spanning tree-DFS-[解题报告]HOJ
2015
09-17

HDU 4582-DFS spanning tree-DFS-[解题报告]HOJ

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:
Microblog Subscription
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)

给定一个无向图,求出它的DFS生成树。

非树边与树边会构成环,现在选择树上的最少的边数,使得每一个环都至少有一条边被选中。

一个环对应的就是树上的一条路径,因为DFS树的性质这条路径只可能是从一个节点出发连向它的儿子。

所以问题就转化成了给定树上的一些简单链,给树上的边染黑白两色,使得每条给定的链上都至少有一条黑边,求最小黑边数量。

假如树是一条长链,则每一个链对应的就是一段区间,就成了经典的贪心问题,只需以右端点为关键字排序然后对于每一个未满足要求的区间尽量往右染即可。

在一般的树上也可以这样贪心,只需按链的父节点的深度为关键字进行排序,尽可能往“高”染色,

#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;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/sd_invol/article/details/9963741