首页 > 代码库 > Graph Theory

Graph Theory

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 140    Accepted Submission(s): 74

 

Problem Description

Little Q loves playing with different kinds of graphs very much. One day he thought about an interesting category of graphs called ``Cool Graph‘‘, which are generated in the following way:
Let the set of vertices be {1, 2, 3, ..., n}. You have to consider every vertice from left to right (i.e. from vertice 2 to n). At vertice i, you must make one of the following two decisions:
(1) Add edges between this vertex and all the previous vertices (i.e. from vertex 1 to i1).
(2) Not add any edge between this vertex and any of the previous vertices.
In the mathematical discipline of graph theory, a matching in a graph is a set of edges without common vertices. A perfect matching is a matching that each vertice is covered by an edge in the set.
Now Little Q is interested in checking whether a ‘‘Cool Graph‘‘ has perfect matching. Please write a program to help him.

 

Input

The first line of the input contains an integer T(1T50), denoting the number of test cases.
In each test case, there is an integer n(2n100000) in the first line, denoting the number of vertices of the graph.
The following line contains n1 integers a2,a3,...,an(1ai2), denoting the decision on each vertice.

 

Output

For each test case, output a string in the first line. If the graph has perfect matching, output ‘‘Yes‘‘, otherwise output ‘‘No‘‘.

 

Sample Input

 

3
2
1
2
2
41 1 2

 

 

 

Sample Output

Yes

No

No

 

// 题意很难懂啊。。。一个 1-n 长,为 n 的一排点,对于每一个点,从左到右,有两种操作中的一个 (1)对于之前的点,每个连条边 (2)什么都不做

问是否存在一个边的集合,所有点两个一组相连,没有孤立点。

题解:很奇怪的一个题,就是不太懂题意,懂了的话还是很简单的。

 

技术分享
 1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 using namespace std; 5 #define MX 100005 6  7 int n; 8 int data[MX]; 9 10 int main()11 {12     int T;13     cin>>T;14     while (T--)15     {16         scanf("%d",&n);17         for (int i=2;i<=n;i++)18             scanf("%d",&data[i]);19         if (n%2)20         {21             printf("No\n");22             continue;23         }24         int ok = 1;25         int cnt = 0;26         for (int i=n;i>=2;i--)27         {28             if (data[i]==1) cnt++;29             else cnt--;30             if (cnt<0)31             {32                 ok=0;33                 break;34             }35         }36         if (ok)37             printf("Yes\n");38         else39             printf("No\n");40     }41     return 0;42 }
View Code

 

 

 

Graph Theory