Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <algorithm>
- using namespace std;
- const int maxn = 300;
- vector <int> G[maxn];
- int k, n;
- int del[maxn];
- int h[maxn];
- int cnt = 0;
- int main() {
- scanf("%d%d", &k, &n);
- if (n >= 10 * k) {
- printf("possible");
- return 0;
- }
- for (int i = 0; i < n; ++i) {
- int d;
- scanf("%d", &d);
- G[i].resize(d);
- for (int j = 0; j < d; ++j) {
- scanf("%d", &G[i][j]);
- --G[i][j];
- }
- }
- while (true) {
- int v = -1;
- for (int i = 0; i < n; ++i) {
- h[i] = 0;
- for (int j = 0; j < (int)G[i].size(); ++j) {
- int u = G[i][j];
- if (del[u] == 0) ++h[i];
- }
- if (del[i] == 0 && (v == -1 || h[v] > h[i])) {
- v = i;
- }
- }
- if (v == -1) break;
- ++cnt;
- del[v] = 1;
- for (int j = 0; j < (int)G[v].size(); ++j) {
- del[G[v][j]] = 1;
- }
- }
- if (cnt >= k) {
- printf("possible");
- } else {
- printf("impossible");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement