Tree-perfect-matching

程式簡介

簡述

使用 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