CodeForces #562 Div2 B. Pairs

Problem - B - Codeforces

概要

1以上n以下の整数(ai, bi)のペアがm個与えられる。同じペアのai, biは異なる。
整数x, yを適切に選ぶことにより、「全てのペアについて、ai, bi の少なくとも1つがxまたはyと等しい」という状態にできればYESを出力し、そのようなx, yが存在しなければNOを出力せよ。

制約

2 ≦ n ≦ 300 000
1 ≦ m ≦ 300 000

方針

整数のうち片方xを固定すると、もう片方の整数yは次の条件を満たすものとなる。
「ai, biの両方がxでないペアについて、どちらかがyである」
これは、ai, biの両方がxでないペアに出現する数字の個数を数えることで見つけることができる。
xを探す範囲だが、片方の整数はかならずa0とb0のどちらかになるため、a0とb0を試せば十分である。

解答

Submission #54781815 - Codeforces

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)

using namespace std;

typedef long long ll;

int n, m;
vector<int> a, b;

bool check(int x){
	int cnt = 0;
	vector<int> v(n+1);
	rep(i, m){
		if(a[i] != x && b[i] != x){
			v[a[i]]++;
			v[b[i]]++;
			cnt++;
		}
	}

	sort(v.begin(), v.end(), greater<int>());
	return v[0] >= cnt;
}


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> n >> m;

	a.resize(m);
	b.resize(m);

	rep(i, m){
		cin >> a[i] >> b[i];
	}

	if(check(a[0])){
		cout << "YES" << endl;
		return 0;
	}

	if(check(b[0])){
		cout << "YES" << endl;
		return 0;
	}

	cout << "NO" << endl;
}