【题意】

有N个城市，城市之间有N-1条路（其实就是一棵树），国王想把直接连在一起的两个城市组合成一个defending unit，一个城市只能属于一个defending unit，给定一个图，求最后是否能把所有的城市都两两配对。

【思路】

如果说算法的话，感觉像是贪心吧。

若输入的城市数目为奇数，那当然是不能配对的，直接就“No”了。

用一个队列存放输入的时候邻边数目为1的点，从队头开始判断，对于队列中每一个点，将该点和该点相邻的点（t2）标记为访问过，然后将t2相邻的点中每一个t3删去t2，若删去之后邻边数为1，则把它放到队列里面。如果删去以后没有邻边了，说明该点被孤立了，也是No，全部点都访问了，就是Yes。

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 using namespace std; 8 int main() 9 {10 int t;11 scanf("%d",&t);12 while(t--)13 {14 int n;15 scanf("%d",&n);16 vector
           
             a[n+1];17 bool vis[n+1];18 memset(vis,false,sizeof(vis));19 20 int u,v;21 for(int i=1;i<=n-1;i++)22 {23 scanf("%d%d",&u,&v);24 a[u].push_back(v);25 a[v].push_back(u);26 }27 if(n % 2 == 1)28 {printf("No\n");continue;}29 30 queue
            
              q;31 for(int i=1;i<=n;i++)32 {33 if(a[i].size() == 1)34 q.push(i);35 }36 37 bool b = true,b2=true;38 int t1,t2,t3;39 while(!q.empty())40 {41 t1 = q.front();42 q.pop();43 if(vis[t1])continue;44 vis[t1] = true;45 t2 = a[t1][0];46 if(vis[t2] == true)47 {48 b = false;49 break;50 }51 vis[t2] = true; 52 for(int i=0;i