Cell Phone Network

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 5735Accepted: 2053
Description

Farmer John has decided to give each of his cows a cell phone in hopes to encourage their social interaction. This, however, requires him to set up cell phone towers on his N (1 ≤ N ≤ 10,000) pastures (conveniently numbered 1…N) so they can all communicate.

Exactly N-1 pairs of pastures are adjacent, and for any two pastures A and B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B) there is a sequence of adjacent pastures such that A is the first pasture in the sequence and B is the last. Farmer John can only place cell phone towers in the pastures, and each tower has enough range to provide service to the pasture it is on and all pastures adjacent to the pasture with the cell tower.

Help him determine the minimum number of towers he must install to provide cell phone service to each pasture.

Input

  • Line 1: A single integer: N
  • Lines 2…N: Each line specifies a pair of adjacent pastures with two space-separated integers: A and B

Output

  • Line 1: A single integer indicating the minimum number of towers to install

Sample Input
5
1 3
5 2
4 3
3 5

Sample Output
2

题目大意：John想让他的所有牛用上手机以便相互交流，他需要建立

几座信号塔在N块草地中。已知与信号塔相邻的草地能收到信号。给你N-1个草地(A，B)

的相邻关系，问：最少需要建多少个信号塔能实现所有草地都有信号。

这就是一个简单的最小支配集的裸题。

什么是最小支配集呢？

最小支配集：值从所有顶点中取尽量少的点组成一个集合，使得剩下的所有点都与取出来的点有边相连。顶点个数最小的支配集被称为最小支配集。

贪心步骤：

1.以1号点深度优先搜索整棵树，求出每个点在DFS中的编号和每个点的父亲节点编号。
2.按DFS的反向序列检查，如果当前点既不属于支配集也不与支配集中的点相连，且它
的父亲也不属于支配集，将其父亲点加入支配集，支配集个数加1。
3.标记当前结点、当前结点的父节点(属于支配集)、当前结点的父节点的父节点(与支配集
中的点相连）

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n,vis[N],f[N];
vector<int> v1[N],pos;
void dfs(int x){//先dfs找到每个节点的父亲节点，和每个节点的时间戳
	pos.emplace_back(x);
	for(int i=0;i<v1[x].size();i++){
		if(!vis[v1[x][i]]){
			vis[v1[x][i]]=1;
			f[v1[x][i]]=x;
			dfs(v1[x][i]);
		}
	}
}
int greedy(){
	int res=0;	int s[N]={0};	int st[N]={0};//是否属于支配集 
	for(int i=n-1;i>=0;i--){
		int t=pos[i];
		if(!s[t]){//如果当前的点没有被支配
			if(!st[f[t]]){//如果父亲不在支配集中
				res++;	st[f[t]]=1;	
			}
			s[t]=1;	s[f[t]]=1;	s[f[f[t]]]=1;//最后标记这三个点
		}
	}
	return res;
}
int main(){
	cin>>n;
	if(n==1){
		cout<<1<<endl;	return 0;
	}
	for(int i=1;i<n;i++){
		int a,b;	cin>>a>>b;	v1[a].emplace_back(b);
		v1[b].emplace_back(a);
	}
	vis[1]=1;	f[1]=1;  dfs(1);
	cout<<greedy()<<endl;
	return 0;
}