Codeforces Round #562 (Div. 2) B题 Pairs

题目链接:http://codeforces.com/contest/1169/problem/B

Codeforces Round #562 (Div. 2)  B题 Pairs

Codeforces Round #562 (Div. 2)  B题 Pairs


题意:给你 m 对数 ,问你能不能在 1 − n 之间找到俩个不相等的 x 和 y 使得 对于前面每一对之中至少有一个数可以等于 x 或 y,找得到输出 YES,否则输出NO。

思路:假设第一对为(a‚b),若x ,y存在,那么他们其中之一就在第一对(a‚b)中,那么如果存在(c,d)使得 c,d 与 a,b 完全不同,那么 x 和 y 另一个数就在(c,d)中,所以 x–y 就是    a–c、 a–d、 b–c、 b–d这四种组合的一种。如果不存在(c,d),那么说明a和b 就能满足,我们只要对所有的 m 对数检查 a–b、a–c、 a–d、 b–c、 b–d这 5 种组合能否满足即可,复杂度Ο(5m)。

AC代码:

 

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 3e5+5;
 4 pair< int ,int > pa[maxn];
 5 int n,m;
 6 bool check(int a,int b)
 7 {
 8     for(int i = 0;i < m;i++)
 9     {
10         if(pa[i].first != a && pa[i].first != b && pa[i].second != a && pa[i].second != b) return  false;
11     }
12     return true;
13 }
14 int main()
15 {
16     cin >> n >> m;
17     int a,b,c = 0,d = 0;
18     for(int i = 0;i < m;i++)
19     {
20         scanf("%d %d",&pa[i].first,&pa[i].second);
21         if(i == 0) a = pa[i].first,b = pa[i].second;
22         if(a != pa[i].first && a != pa[i].second && b != pa[i].first && b != pa[i].second)
23          c = pa[i].first,d = pa[i].second;
24     }
25     bool flag = false;
26     if(check(a,b)||check(a,c)||check(a,d)||check(b,c)||check(b,d) ) flag = true;
27     if(flag) cout << "YES" << endl;
28     else cout << "NO" << endl;
29     return 0;
30 }

 

上一篇:Codeforces Round #562 (Div. 2)


下一篇:Struts2框架里面action与前端jsp页面进行交互路径问题---》一个对话框里面有很多超链接,进行相应的跳转