Pair

| Comments

Description Time Limit:1sec Memory Limit:256MB

The N cities of Estiah are connected by N-1 roads. The roads are built in a way that it’s always possible to travel between any two cities. Now the king of Estiah wants to pair adjacent cities into defending units. Two cities are adjacent if they are connected directly by a road. Each defending unit consists of exactly two cities, and each city can never be paired into two different defending units. What the king wants to know is if it’s possible to have all the cities paired into defending units. Can you help him ?

Input

The input consists of several test cases. The first line of the input is an positive integer indicating the number of test cases following. Each test case starts with an positive integer N (1<=N<=10000) , which is the number of cities. Cities are numbered from 1 to N. The next N-1 lines each contains two positive integer A and B, indicating that there is a road connecting city A and city B.

Output

For each test case, output a line containing “Yes” if there is a way to pair all the cities, or “No” otherwise.

挺有意思的一道小题。定义：没有回路的连通图为树。对于图G=(V,E),V=N,|E|=N-1,显然这里的无向连通图即为树。要判断图是否能将连通的节点两两配对，看似无从下手，其实这里要用到贪心思想，首先找出一个配对原则：一棵树的叶子节点要配对，显然只有跟它的父节点配对。所以我们可以从叶子节点入手，把整个问题划分为所有叶子节点是否能完全配对，若所有叶子节点（度数为1的节点，删除一个节点后，相邻节点可能成为新叶子)都能配对，则Yes。因为题中N<=10000,所以邻接矩阵会超时，这里用邻接表，vector,list,set都行，并用栈或队列存储叶子节点。

顺便吐嘈一下我们学院，除了做ACM题，其他都被弱化了，尤其是操作系统和计算机网络，教学和实践做的太不好了，一味的鼓励刷题，这不是真正的计算机专业，算法很重要，但是过度强调竞赛，就变成了另一个奥数，毁新手不倦。

节点配对
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

#include<stdio.h>
#include<set>
#include<string.h>
#include<stack>
using namespace std;

set<int> adj[10001];//存储邻接表
int deg[10001];//保存节点度数
int del[10001];//判断节点是否配对，即是否被删除
stack<int> leaf;//保存叶子节点入栈

int main()
{
    int t;
  scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        memset(deg, 0, sizeof(deg));
        memset(del, 0, sizeof(del));
      while(!leaf.empty())
            leaf.pop();
        for(int i=0; i<10001; i++)
            adj[i].clear();
        for(int i=1; i<=n-1; i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            adj[a].insert(b);//无向图
            adj[b].insert(a);
            deg[a]++;
            deg[b]++;
        }
        for(int i=1; i<=n ;i++)
            if(deg[i]==1)
                leaf.push(i);
      while(!leaf.empty())
        {
            int v=leaf.top();
            leaf.pop();
            if(!adj[v].empty())
            {
              int j=*(adj[v].begin());
              for(set<int>::iterator it=adj[j].begin(); it!=adj[j].end(); it++)
              {
                  adj[*it].erase(j);//与被删除节点相邻的边都删除
                  deg[*it]--;
                  if(deg[*it]==1 && del[*it]==0)
                  {
                      leaf.push(*it);//如果这个节点此时度数为1，入栈
                  }
              }
              del[v]=1;//删除配对成功的两个节点
              del[j]=1;
          }
        }
        int ok=1;
        for(int i=1; i<=n; i++)
            if(del[i]==0)
            {
                ok=0;
                break;
            }
        if(ok==1 && n%2==0)//只有偶数个节点才能配对
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}