hdu 6029 Graph Theory 思维
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
题目：
http://acm.hdu.edu.cn/showproblem.php?pid=6029
题意：
有n个点，有下面两种操作
- 从当前点向前面所有点连一条边
- 从当前点不向任何点连边
问构成的图是不是一个二分图
思路：
奇数肯定不能构成二分图，偶数的话，我们依次判断，记录没有配对的点数，当操作1时，查看是否有没有配对的点，有的话，把当前点和某个未配对的点配对，那么未配对点数减1，没有的话，当前点就是一个未配对点，相应的加1，操作2的话， 当前点一定是一个未配对点，相应加1，最后检查未配对点数是不是0即可
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;
int a[N];
int main()
{
int t, n;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(int i = 1; i <= n-1; i++) scanf("%d", &a[i]);
if(n & 1) puts("No");
else
{
int val = 1;
for(int i = 1; i <= n-1; i++)
{
if(a[i] == 1)
{
if(val == 0) val++;
else val--;
}
else val++;
}
puts(val ? "No" : "Yes");
}
}
return 0;
}
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |