SPOJ - UOFTCG 树的最小路径覆盖

 1 //SPOJ - UOFTCG 树的最小路径覆盖
 2 
 3 #include <bits/stdc++.h>
 4 #include <vector>
 5 using namespace std;
 6 #define ll long long
 7 const int mod = 1e9+7;
 8 const int maxn=510;
 9 const int N = 1e5+10;
10 int cnt;
11 int head[N];
12 struct edge{
13     int to,next;
14 }e[N<<2];
15 void addedge(int u,int v){
16     e[cnt].to=v,e[cnt].next=head[u],head[u]=cnt++;
17     e[cnt].to=u,e[cnt].next=head[v],head[v]=cnt++;
18 }
19 
20 int cov[N];
21 bool vis[N],used[N];
22 void dfs(int u,int f){
23     used[u]=1;
24     cov[u]=1;
25     int tot=0;
26     for(int i=head[u];~i;i=e[i].next){
27         int v=e[i].to;
28         if(v==f) continue;
29         dfs(v,u);
30         cov[u]+=cov[v];
31         if(!vis[v]) tot++;
32     }
33     if(tot>=2) cov[u]-=2,vis[u]=1;
34     else if(tot==1) cov[u]-=1;
35 }
36 int main(){
37     // freopen("in.txt","r",stdin);
38     int T;
39     scanf("%d",&T);
40     while(T--){
41         cnt=0;
42         memset(used,false,sizeof(used));
43         memset(head,-1,sizeof(head));
44         memset(cov,0,sizeof(cov));
45         memset(vis,false,sizeof(vis));
46         int n,m;
47         scanf("%d%d",&n,&m);
48         for(int i=1;i<=m;i++){
49             int u,v;
50             scanf("%d%d",&u,&v);
51             addedge(u,v);
52         }
53         int ans=0;
54         for(int i=1;i<=n;i++){
55            if(!used[i]) dfs(i,0),ans+=cov[i];
56         }
57         // cout<<cov[1]<<endl;
58         printf("%d\n",ans+n-1);
59     }
60 }