Advertisement
Guest User

Untitled

a guest
Jun 21st, 2018
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.78 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. vector<int> used;
  6. vector<int> r;
  7. vector<vector<int>> g;
  8.  
  9. bool dfs(int v, int c)
  10. {
  11. if(used[v] == c)
  12. {
  13. return false;
  14. }
  15. used[v] = c;
  16. for(int i : g[v])
  17. {
  18. if(r[i] == -1)
  19. {
  20. r[i] = v;
  21. return true;
  22. }
  23. }
  24. for(int i : g[v])
  25. {
  26. if(dfs(r[i], c))
  27. {
  28. r[i] = v;
  29. return true;
  30. }
  31. }
  32. return false;
  33. }
  34.  
  35. int main()
  36. {
  37. ios_base::sync_with_stdio(false);
  38. cin.tie(0);
  39. int n;
  40. cin >> n;
  41. r.resize(n * 2, -1);
  42. used.resize(n * 2);
  43. g.resize(n);
  44. set<set<string>> V;
  45. for(int i = 0; i < n; ++i)
  46. {
  47. int k;
  48. cin >> k;
  49. set<string> local;
  50. for(int j = 0; j < k; ++j)
  51. {
  52. string s1;
  53. cin >> s1;
  54. local.insert(s1);
  55. }
  56. V.insert(local);
  57. }
  58. vector<set<string>> v;
  59. for(auto i : V)
  60. {
  61. v.push_back(i);
  62. }
  63.  
  64. for(int i = 0; i < v.size(); ++i)
  65. {
  66. for(int j = 0; j < v.size(); ++j)
  67. {
  68. if(i == j) continue;
  69. bool st = true;
  70.  
  71. for(auto x : v[i])
  72. {
  73. if(v[j].find(x) == v[j].end())
  74. {
  75. st = false;
  76. break;
  77. }
  78. }
  79. if(st)
  80. {
  81. g[i].push_back(n + j);
  82. }
  83. }
  84. }
  85. int ans = 0;
  86. // for(int i = 0; i < n; ++i)
  87. // {
  88. // g[i].push_back(i + n);
  89. // }
  90. int c = 1;
  91. for(int i = 0; i < n; ++i)
  92. {
  93. if(dfs(i, c)) {
  94. ++ans;
  95. ++c;
  96. }
  97. }
  98. cout << v.size() - ans;
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement