Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2346
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2346
Back to the Future
By Bruno Junqueira 
Brazil
Timelimit: 1
Doctor Emmet is working on a safer device to travel in time. He gathered N different and rare pieces of metal. Each piece may be compatible with some other different pieces. He has a complete list with M distinct pairs of compatible metals. Any pair of metals that is not on the list is incompatible.
In order for the device to work, he must choose a set of metals such that each of them is compatible with at least A others in that set. However, in order to preserve some balance, they must also be incompatible with at least B others in that set.
More metals mean more energy and a safer device. This is why Doctor Emmet needs your help, he wants to know the size of the largest set he can choose that meets these criteria.
Input
The first line contains four integers N, M, A and B, representing respectively how many different pieces of metal exist (1 ≤ N ≤ 105), how many compatibilities there are (1 ≤ M ≤ 105) and the variables A and B described in the problem statement (0 ≤ A,B < N). The different metals are conveniently numbered from 1 to N. Each of the following M lines contains two integers X and Y corresponding to a pair of compatible metals (1 ≤ X, Y ≤ N with X ≠Y). There are no repeated pairs in the input.
Output
Output a line with one integer representing the size of the largest set of metals satisfying the requirements specified in the problem statement.
| Input Samples | Output Samples |
|
3 1 1 0 |
2 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#include <set>
#include <vector>
#define MAXN 100010
#define MP make_pair
using namespace std;
typedef pair < int, int> ii;
vector<int> grafo[MAXN];
int grau[MAXN], n, m, a, b, deletado[MAXN];
set < ii> conjunto;
int main() {
scanf("%d %d %d %d", &n, &m, &a, &b);
for (int i = 1; i < = m; i++) {
int u, v;
scanf("%d %d", &u, &v);
grafo[u].push_back(v);
grafo[v].push_back(u);
grau[u]++;
grau[v]++;
}
for (int i = 1; i < = n; i++) {
conjunto.insert(MP(grau[i], i));
}
for (int vez = 0; vez < n && !conjunto.empty(); vez++) {
ii candidato1 = *(conjunto.begin());
int v1 = candidato1.second, g1 = candidato1.first;
if (g1 < a) {
// printf("%d %d 1\n",v1,g1);
conjunto.erase(candidato1);
deletado[v1] = 1;
for (int i = 0; i < grafo[v1].size(); i++) {
int p = grafo[v1][i];
if (deletado[p]) continue;
conjunto.erase(conjunto.find(MP(grau[p], p)));
grau[p]--;
conjunto.insert(MP(grau[p], p));
}
}
if (conjunto.empty()) break;
ii candidato2 = *(conjunto.rbegin());
int v2 = candidato2.second, g2 = candidato2.first;
if ((int)conjunto.size() - g2 - 1 < b) {
// printf("%d %d 2\n",v2,g2);
conjunto.erase(candidato2);
deletado[v2] = 1;
for (int i = 0; i < grafo[v2].size(); i++) {
int p = grafo[v2][i];
if (deletado[p]) continue;
conjunto.erase(conjunto.find(MP(grau[p], p)));
grau[p]--;
conjunto.insert(MP(grau[p], p));
}
}
}
printf("%d\n", (int)conjunto.size());
return 0;
}
Input
1 2
Output