Advertisement
Guest User

Untitled

a guest
Nov 22nd, 2014
156
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>  
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 300;
  9.  
  10. vector <int> G[maxn];
  11.  
  12. int k, n;
  13.  
  14. int del[maxn];
  15. int h[maxn];
  16. int cnt = 0;
  17.          
  18. int main() {
  19.     scanf("%d%d", &k, &n);
  20.     if (n >= 10 * k) {
  21.         printf("possible");
  22.         return 0;
  23.     }
  24.  
  25.     for (int i = 0; i < n; ++i) {
  26.         int d;
  27.         scanf("%d", &d);
  28.         G[i].resize(d);
  29.         for (int j = 0; j < d; ++j) {
  30.             scanf("%d", &G[i][j]);
  31.             --G[i][j];
  32.         }
  33.     }
  34.  
  35.     while (true) {
  36.         int v = -1;
  37.         for (int i = 0; i < n; ++i) {
  38.             h[i] = 0;
  39.             for (int j = 0; j < (int)G[i].size(); ++j) {
  40.                 int u = G[i][j];
  41.                 if (del[u] == 0) ++h[i];
  42.             }
  43.             if (del[i] == 0 && (v == -1 || h[v] > h[i])) {
  44.                 v = i;
  45.             }
  46.         }
  47.         if (v == -1) break;
  48.         ++cnt;
  49.         del[v] = 1;
  50.         for (int j = 0; j < (int)G[v].size(); ++j) {
  51.             del[G[v][j]] = 1;
  52.         }
  53.     }
  54.     if (cnt >= k) {
  55.         printf("possible");
  56.     } else {
  57.         printf("impossible");
  58.     }
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement