首页 > 代码库 > hdu 6029 Graph Theory

hdu 6029 Graph Theory

题目链接:hdu 6029 Graph Theory

题意:

有n个点,每个点按标号排序,现在每个点有两种操作,1表示将这个点和之前全部的点连一条边,2表示没有操作。

现在问你是否有一个边集能构成完美匹配。

完美匹配的定义为:1.每个点有且只有一条边。2.每条边的两端都没有重叠的点。

题解:

首先n为奇数的时候肯定是不行的,然后对于n为偶数的时候for一遍,看看有哪些点没有被匹配到。

技术分享
 1 #include<cstdio>
 2 int t,n,x,cnt;
 3 int main(){
 4     scanf("%d",&t);
 5     while(t--){
 6         scanf("%d",&n),cnt=1;
 7         for(int i=1;i<n;i++){
 8             scanf("%d",&x);
 9             if(x==1&&cnt)cnt--;
10             else if(x==2)cnt++;
11         }
12         puts((cnt||n&1)?"No":"Yes");
13     }
14     return 0;
15 }
View Code

 

hdu 6029 Graph Theory