CF-1169B Pairs 题解

题目大意

给定你m对整数对（x[i],y[i]），请问是否存在x和y，使得n对中每一对中至少有一个数是x和y之中的一个。

解题思路

（我是真的蠢啊。。。

每一对都要是x，y中的一个，那么x就只有两种情况，第一对其中的任意一个。

这个需要只需要枚举y两次即可。

（就是这个卡了我好久。。

只要x加上y减去y和x一起出现的次数加起来等于m即可。

完整代码

#include <iostream>
#include <algorithm>
#include <map>
#include <functional>
using namespace std;

const int N = 3e5 + 5;
int cnt[N];
map<pair<int,int>, int> M;

int main() {
	int n, m;
	cin >> n >> m;
	int a, b;
	cin >> a >> b;
	cnt[a]++;
	cnt[b]++;
	M[make_pair(a, b)]++;
	M[make_pair(b, a)]++;
	for (int i = 1; i < m; i++) {
		int x, y;
		cin >> x >> y;
		cnt[x]++;
        cnt[y]++;
		M[make_pair(x,y)]++;
		M[make_pair(y,x)]++;
	}
	for (int i = 1; i <= n; i++) {
		if (i != a&& cnt[i] + cnt[a] - M[make_pair(i, a)] == m) {
			cout << "YES" << endl;
			return 0;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (i!=b&&cnt[i] + cnt[b] - M[make_pair(i, b)] == m) {
			cout << "YES" << endl;
			return 0;
		}
	}
	cout << "NO"<< endl;
}