題目鏈接

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