题目链接:http://codeforces.com/contest/1169/problem/B
题意:给你 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 }