SHARE
TWEET

Untitled

a guest Dec 14th, 2019 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4.  
  5.  
  6. enum Color {
  7.     WHITE,
  8.     GRAY,
  9.     BLACK
  10. };
  11.  
  12.  
  13. class Graph {
  14. private:
  15.  
  16.     std::vector < std::vector<size_t>> data;
  17.  
  18. public:
  19.  
  20.     Graph(size_t N);
  21.  
  22.     ~Graph(){}
  23.  
  24.     void AddEdge(size_t from, size_t to);
  25.  
  26.     size_t Addition();
  27.  
  28.     std::vector<std::vector<size_t>> Strong_Connectivity();
  29.  
  30.     Graph Inversion() const;
  31.  
  32.     void DFS(size_t from, std::vector<Color>& Colors, std::vector<std::pair<size_t, size_t>>& time_out, size_t& time);
  33.  
  34.     void DFS(size_t from, std::vector<Color>& Colors, std::vector<size_t>& component);
  35.  
  36.     std::vector<std::pair<size_t, size_t>> DFS_Full();
  37.  
  38.     std::vector<std::vector<size_t>> DFS_Full(std::vector<size_t> order);
  39.  
  40.     std::vector<size_t> GetVertices(size_t from);
  41. };
  42.  
  43.  
  44. Graph::Graph(size_t N) {
  45.     for (size_t i = 0; i < N; ++i) {
  46.         std::vector<size_t> tmp;
  47.         this->data.push_back(tmp);
  48.     }
  49. }
  50.  
  51.  
  52. void Graph::AddEdge(size_t from, size_t to) {
  53.     if (from != to) {
  54.         this->data.at(from).push_back(to);
  55.     }
  56. }
  57.  
  58.  
  59. std::vector<size_t> Graph::GetVertices(size_t from) {
  60.     return this->data.at(from);
  61. }
  62.  
  63.  
  64. void Graph::DFS(size_t from, std::vector<Color>& Colors, std::vector<std::pair<size_t, size_t>>& time_out, size_t& time) {
  65.     Colors.at(from) = GRAY;
  66.     std::vector<size_t> to = this->GetVertices(from);
  67.     for (size_t i = 0; i < to.size(); ++i) {
  68.         if (Colors.at(to.at(i)) == WHITE) {
  69.             time++;
  70.             this->DFS(to.at(i), Colors, time_out, time);
  71.         }
  72.     }
  73.     Colors.at(from) = BLACK;
  74.     time_out.at(from).second = ++time;
  75. }
  76.  
  77.  
  78. std::vector<std::pair<size_t, size_t>> Graph::DFS_Full() {
  79.     std::vector<Color> Colors;
  80.     for (size_t i = 0; i < this->data.size(); ++i) Colors.push_back(WHITE);
  81.     std::vector<std::pair<size_t, size_t>> time_out;
  82.     for (size_t i = 0; i < this->data.size(); ++i) time_out.push_back(std::make_pair(i, 0));
  83.     size_t time = 1;
  84.  
  85.     for (size_t i = 0; i < this->data.size(); ++i) {
  86.         if (Colors.at(i) != WHITE) continue;
  87.         this->DFS(i, Colors, time_out, time);
  88.         time++;
  89.     }
  90.  
  91.     return time_out;
  92. }
  93.  
  94.  
  95. std::vector<std::vector<size_t>> Graph::DFS_Full(std::vector<size_t> order) {
  96.     std::vector<Color> Colors;
  97.     for (size_t i = 0; i < order.size(); ++i) Colors.push_back(WHITE);
  98.     std::vector < std::vector<size_t>> components;
  99.  
  100.     for (size_t i = 0; i < order.size(); ++i) {
  101.         if (Colors.at(order.at(i)) == WHITE) {
  102.             std::vector<size_t> component;
  103.             this->DFS(order.at(i), Colors, component);
  104.             components.push_back(component);
  105.         }
  106.     }
  107.  
  108.     return components;
  109. }
  110.  
  111.  
  112. void Graph::DFS(size_t from, std::vector<Color>& Colors, std::vector<size_t>& component) {
  113.     component.push_back(from);
  114.     Colors.at(from) = GRAY;
  115.     std::vector<size_t> to = this->GetVertices(from);
  116.  
  117.     for (size_t i = 0; i < to.size(); ++i) {
  118.         if (Colors.at(to.at(i)) == WHITE) {
  119.             DFS(to.at(i), Colors, component);
  120.         }
  121.     }
  122.     Colors.at(from) = BLACK;
  123. }
  124.  
  125.  
  126. Graph Graph::Inversion() const{
  127.     Graph Inv(this->data.size());
  128.     for (size_t i = 0; i < this->data.size(); ++i) {
  129.         for (size_t j = 0; j < this->data.at(i).size(); ++j) {
  130.             Inv.AddEdge(this->data.at(i).at(j), i);
  131.         }
  132.     }
  133.     return Inv;
  134. }
  135.  
  136.  
  137. bool comp(std::pair<size_t, size_t> p1, std::pair<size_t, size_t> p2) {
  138.     return p1.second > p2.second;
  139. }
  140.  
  141.  
  142. std::vector<std::vector<size_t>> Graph::Strong_Connectivity() {
  143.     std::vector<std::pair<size_t, size_t>> time_out = this->Inversion().DFS_Full();
  144.     sort(time_out.begin(), time_out.end(), comp);
  145.     std::vector<size_t> order;
  146.     for (size_t i = 0; i < time_out.size(); ++i) {
  147.         order.push_back(time_out.at(i).first);
  148.     }
  149.     return this->DFS_Full(order);
  150. }
  151.  
  152.  
  153. void Search_Two_numbers(std::vector<size_t> vec, bool& first, bool& second, std::pair<size_t, size_t> digit) {
  154.     for (size_t i = 0; i < vec.size(); ++i) {
  155.         if (digit.first == vec.at(i)) first = true;
  156.         if (digit.second == vec.at(i)) second = true;
  157.     }
  158. }
  159.  
  160.  
  161. size_t Graph::Addition() {
  162.     std::vector<std::vector<size_t>> components = this->Strong_Connectivity();
  163.     if (components.size() == 1) return 0;
  164.     std::vector<bool> Enter, Exit;
  165.     for (size_t i = 0; i < components.size(); ++i) {
  166.         Enter.push_back(true);
  167.         Exit.push_back(true);
  168.     }
  169.     for (size_t i = 0; i < this->data.size(); ++i) {
  170.         for (size_t j = 0; j < this->data.at(i).size(); ++j) {
  171.             std::pair<size_t, size_t> Edge{ i, data.at(i).at(j) };
  172.             for (size_t k = 0; k < components.size(); ++k) {
  173.                 bool first{ false }, second{ false };
  174.                 if (!Exit.at(k) && !Enter.at(k)) continue;
  175.                 Search_Two_numbers(components.at(k), first, second, Edge);
  176.                 if (first && !second) Exit.at(k) = false;
  177.                 if (!first && second) Enter.at(k) = false;
  178.             }
  179.         }
  180.     }
  181.  
  182.     size_t en{ 0 }, ex{ 0 };
  183.     for (size_t i = 0; i < Enter.size(); ++i) {
  184.         en += Enter.at(i);
  185.         ex += Exit.at(i);
  186.     }
  187.     return (en > ex) ? en : ex;
  188. }
  189.  
  190.  
  191. int main()
  192. {
  193.     size_t N_vectices, N_Edges;
  194.  
  195.     std::cin >> N_vectices >> N_Edges;
  196.  
  197.     Graph enter(N_vectices);
  198.  
  199.     for (size_t i = 0; i < N_Edges; ++i) {
  200.         size_t tmp1, tmp2;
  201.         std::cin >> tmp1 >> tmp2;
  202.         enter.AddEdge(tmp1 - 1, tmp2 - 1);
  203.     }
  204.  
  205.     std::cout << enter.Addition() << std::endl;
  206.  
  207.     system("pause");
  208.     return 0;
  209. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top