Advertisement
Guest User

Untitled

a guest
Oct 16th, 2018
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.76 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int n;
  6. vector<vector<int>> r_Adjacency_list() {
  7. cin >> n;
  8. vector<vector<int>> forest(n, vector<int>(0, 0));
  9. int k;
  10. for (int i; i != n; ++i) {
  11. cin >> k;
  12. for (int j; j != k; ++j) {
  13. cin >> k;
  14. forest[i].push_back(k);
  15. }
  16. }
  17. }
  18.  
  19. vector<bool> used(n, false);
  20. void dfs (const int& v, const vector<vector<int>>& forest, vector<int>& tree) {
  21. /// if (!used[v]) {
  22. used[v] = true;
  23. tree.push_back(v);
  24. for (auto i : forest[v]) {
  25. if (!used[i]) {
  26. dfs(i, forest, tree);
  27. }
  28. }
  29. /// }
  30. }
  31.  
  32. vector<vector<int>> find_trees(const vector<vector<int>>& adjacency_list) {
  33. vector<vector<int>> trees;
  34. for (int i = 0; i != n; ++i) {
  35. if (!used[i]) {
  36. vector<int> tree;
  37. dfs(i, adjacency_list, tree);
  38. trees.push_back(tree);
  39. }
  40. }
  41. }
  42.  
  43. vector<int> s(n, 0);
  44. vector<int> bez(n, 0);
  45. int vertex_cover(const vector<int>& tree, const vector<vector<int>>& forest) {
  46. if (tree.size() == 1) return 1;
  47. for (auto i : tree) {
  48. if (forest[i][0] == 1) {
  49. s[i] = 1;
  50. bez[i] = 0;
  51. } else {
  52. for (auto j : forest[i]) {
  53. s[i] += min(s[j], bez[j]);
  54. bez[i] = s[j];
  55. }
  56. }
  57. }
  58. for (auto i : tree) {
  59. if (bez[i] != 0) {
  60. return min(bez[i], s[i]);
  61. }
  62. }
  63. }
  64.  
  65. int main() {
  66. vector<vector<int>> forest = r_Adjacency_list();
  67. vector<vector<int>> trees = find_trees(forest);
  68. int k = 0;
  69. for (auto tree : trees) {
  70. k += vertex_cover(tree, forest);
  71. }
  72. cout << k;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement