使用 Depth-First Search ( DFS ) 實作
Give a linear-time algorithm that takes as input a tree ( undirected tree ) and determines whether it has a perfect matching: a set of edges that touches each node exactly once.
- Input：the first two are maximal node label【contiguous】and the number of edge. The rest are all edges
- Output：Is there a perfect matching, Exist or Doesn't exist
Example 1
Input: 6 5 1 2 1 3 2 4 2 5 3 6
Output: Doesn't exist perfect matching
Example 2
Input: 4 3 1 2 1 3 2 4
Output: Exist perfect matching
Example 3
Input: 6 5 1 2 1 3 1 4 2 5 3 6
Output: Exist perfect matching
- 0 means it was not matched
O(V+E)：using adjacency list and DFS