SPOJ - UOFTCG(树的路径覆盖,好题)

题目链接

UOFTCG - Office Mates

Dr. Baws has an interesting PRoblem. His N graduate students, while friendly with some select people, are generally not friendly with each other. No graduate student is willing to sit beside a person they aren't friends with.

The desks are up against the wall, in a single line, so it's possible that Dr. Baws will have to leave some desks empty. He does know which students are friends, and fortunately the list is not so long: it turns out that for any subset of Kgraduate students, there are at most K−1 pairs of friends. Dr. Baws would like you to minimize the total number of desks required. What is this minimum number?

Input

The input begins with an integer T≤50, the number of test cases. Each test case begins with two integers on their own line: N≤100000, the number of graduate students (who are indexed by the integers 1 through N), and M, the number of friendships among the students. Following this are M lines, each containing two integers i and j separated by a single space. Two integers i and j represent a mutual friendship between students i and j.

The total size of the input file does not exceed 2 MB.

Output

For each test case output a single number: the minimum number of desks Dr. Baws requires to seat the students.

Example

Input:
16 51 21 31 44 54 6
Output:
7
Explanation of Sample:
As seen in the diagram, you seat the students in two groups of three with one empty desk in the middle.
 Submit solution!
题意：
有N(N <= 100000)个学生，M对朋友关系，学生只能挨着他的朋友坐。
桌子排列成一条直线，可以让一些桌子空出来.
数据保证对于任何含K(K<=N)个学生的集合，最多只有K-1对朋友。
求最少需要多少张桌子。
题解：
这道题可以转化为图的最小路径覆盖。假设点数为n，最小路径覆盖条数为m，答案即为n+m-1。根据题意，发现数据是若干颗树。
那么，对于一棵树，怎么求最小路径覆盖呢？
有两种方法，贪心和树形dp，可参考博客：博客链接
树形dp解至今还没看懂==
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=100000+100;int head[maxn];struct edge{    int from,to,next;}e[maxn*2];   //int tol=0;void add(int u,int v){    e[++tol].to=v,e[tol].next=head[u],head[u]=tol;}int vis[maxn],sum[maxn],used[maxn];void dfs(int u,int fa){    vis[u]=1;    sum[u]=1;    int deg=0;    for(int i=head[u];i;i=e[i].next)    {        int v=e[i].to;        if(v==fa) continue;        dfs(v,u);        sum[u]+=sum[v];        if(!used[v]) deg++;    }    if(deg>=2) used[u]=1,sum[u]-=2;    else if(deg==1) sum[u]-=1;}int main(){    int cas;    scanf("%d",&cas);    while(cas--)    {        memset(vis,0,sizeof(vis));        memset(sum,0,sizeof(sum));        memset(head,0,sizeof(head));        memset(used,0,sizeof(used));        tol=0;        int n,m;        scanf("%d%d",&n,&m);        while(m--)        {            int u,v;            scanf("%d%d",&u,&v);            add(u,v),add(v,u);        }        int ans=0;        rep(i,1,n+1)        {            if(!vis[i]) dfs(i,0),ans+=sum[i];        }        ans=n+ans-1;        printf("%d/n",ans);    }    return 0;}