树的最小路径覆盖：以SPOJ UOFTCG为例
//============================================================================ // Name : tree.cpp // Author : Qihan // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================ #include <bits/stdc++.h> using namespace std; #define pi acos(-1.0) #define Lowbit(x) (x & (-x)) #define lson l,mid,rt << 1 #define rson mid + 1,r,rt << 1 | 1 #define inf 0x3f3f3f const int maxn = (200000 + 10); const int mol = 1000000007; typedef long long int LLI; typedef pair<int,int> PII; struct Edge{ int v; int next; }edge[maxn * 2]; int head[maxn],tot = 0; bool vis[maxn]; bool mark[maxn]; int ans[maxn]; void addedge(int u,int v){ edge[tot].next = head[u]; edge[tot].v = v; head[u] = tot ++; } void dfs(int x,int root){ ans[x] = vis[x] = true; int cnt = 0; for(int i = head[x];i != -1;i = edge[i].next){ if(edge[i].v == root) continue; dfs(edge[i].v,x); ans[x] += ans[edge[i].v]; if(!mark[edge[i].v]) cnt ++; } if(cnt >= 2) ans[x] -= 2,mark[x] = true; else if(cnt == 1) ans[x] --; } int main() { // freopen("/home/qihan/Documents/in","r",stdin); // freopen("/home/qihan/Documents/out1","w",stdout); int t; scanf("%d",&t); while(t --){ int n,m; scanf("%d%d",&n,&m); memset(ans,0,sizeof(ans)); memset(head,-1,sizeof(head)); memset(vis,false,sizeof(vis)); memset(mark,false,sizeof(mark)); for(int i = 1;i <= m;i ++){ int u,v; scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } int re = 0; for(int i = 1;i <= n;i ++){ if(!vis[i]){ dfs(i,0); vis[i] = true; re += ans[i]; } } printf("%d\n",re + n - 1); } return 0; }