Guest User

Untitled

a guest
Jun 23rd, 2018
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.20 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <string>
  5. #include <utility>
  6. #include <algorithm>
  7. #include <cmath>
  8. #include <map>
  9. #include <set>
  10. #include <queue>
  11. using namespace std;
  12.  
  13. typedef long long ll;
  14. typedef long double ld;
  15. typedef pair<int,int> pii;
  16.  
  17. #define pb push_back
  18. #define mp make_pair
  19. #define sz(a) int((a).size())
  20. #define forn(i, n) for (int i=0; i<(n); ++i)
  21.  
  22. const int maxn = 256;
  23.  
  24. vector<int> g[maxn];
  25. bool v1[maxn], v2[maxn];
  26. int mt[maxn], root;
  27. int p[maxn];
  28. int bmt[maxn];
  29. int n;
  30.  
  31.  
  32. bool dfs(int x)
  33. {
  34. if (v1[x]) return false;
  35. v1[x] = v2[x] = true;
  36. forn (i, sz(g[x]))
  37. {
  38. int y = g[x][i];
  39. if (y != root)
  40. if (mt[y] == -1 || (!v2[y] && dfs(mt[y])))
  41. {
  42. mt[x] = y;
  43. mt[y] = x;
  44. return true;
  45. }
  46. }
  47. v2[x] = false;
  48. return false;
  49. }
  50.  
  51. int matching()
  52. {
  53. forn (i, n) mt[i] = -1;
  54. int res = 0;
  55. forn (i, n) if (mt[p[i]] == -1)
  56. {
  57. forn (j, n) v1[j] = v2[j] = false;
  58. root = p[i];
  59. if (dfs(p[i])) ++res;
  60. }
  61. return res;
  62. }
  63.  
  64.  
  65.  
  66. bool solve()
  67. {
  68. if (n % 2 != 0) return false;
  69. forn (i, n) p[i] = i;
  70. int ok = 0, m, f = 0;
  71. forn (it, 10)
  72. {
  73.  
  74. m = matching();
  75. if (m == n/2)
  76. {
  77. if (!f)
  78. {
  79. f = 1;
  80. forn (i, n) bmt[i] = mt[i];
  81. }
  82. int same = 1;
  83. forn (i, n) if (bmt[i] != mt[i]) same = 0;
  84. if (!same) return false;
  85. ok = 1;
  86. }
  87. random_shuffle(p, p+n);
  88. }
  89. if (!ok) return false;
  90. //forn (i, n) printf("%d ", mt[i]); puts("");
  91. return true;
  92. }
  93.  
  94.  
  95. int main()
  96. {
  97. freopen("a.in", "r", stdin);
  98.  
  99. int tc; scanf("%d", &tc);
  100. while (tc--)
  101. {
  102. scanf("%d", &n);
  103. forn (i, n)
  104. {
  105. int m; scanf("%d", &m);
  106. g[i].clear();
  107. forn (j, m)
  108. {
  109. int x; scanf("%d", &x);
  110. g[i].pb(x-1);
  111. }
  112. }
  113. if (solve()) puts("YES"); else puts("NO");
  114. }
  115.  
  116. return 0;
  117. }
Add Comment
Please, Sign In to add comment