Advertisement
Guest User

Untitled

a guest
Dec 11th, 2017
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.19 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. class Graph {
  8. public:
  9.     Graph(int n);
  10.  
  11.     struct Node {
  12.  
  13.         vector<Node *> children;
  14.         int id;
  15.     };
  16.  
  17. //    void add(int a, int b);
  18. //
  19. //    void make(vector<int> &distances);
  20. //
  21. //    void bfsFinal(Node *node, vector<int> &count, vector<int> &countfinal);
  22.    
  23.     vector<Node> nodes;
  24. };
  25.  
  26. void bfs(const Graph& graph const Graph::Node *node, vector<int> &distances, const Graph::Node *&Di){
  27.     graph.nodes    
  28. }
  29.  
  30.  
  31. Graph::Graph(int n) :
  32.         nodes(n) {
  33.     for (int i = 0; i < n; i++) {
  34.         nodes[i].id = i;
  35.     }
  36. }
  37.  
  38. void Graph::add(int vertex1, int vertex2) {
  39.     nodes[vertex2].children.push_back(&nodes[vertex1]);
  40.     nodes[vertex1].children.push_back(&nodes[vertex2]);
  41. }
  42.  
  43. void Graph::bfs(Node *node, vector<int> &count, Node *&Diameter) {
  44.     queue<Node *> myQueue;
  45.     count[node->id] = 0;
  46.     vector<bool> was(count.size());
  47.     was[node->id] = true;
  48.     myQueue.push(node);
  49.     int datediam = 0;
  50.     while (!myQueue.empty()) {
  51.         Node *vertex = myQueue.front();
  52.         myQueue.pop();
  53.         for (int i = 0; i < vertex->children.size(); i++) {
  54.             if (vertex->children[i] != nullptr && was[vertex->children[i]->id] == false) {
  55.                 myQueue.push(vertex->children[i]);
  56.                 was[vertex->children[i]->id] = true;
  57.                 count[vertex->children[i]->id] = count[vertex->id] + 1;
  58.                 if (count[vertex->children[i]->id] > datediam) {
  59.                     datediam = count[vertex->children[i]->id];
  60.                     Diameter = vertex->children[i];
  61.                 }
  62.             }
  63.         }
  64.     }
  65. }
  66.  
  67. void Graph::bfsFinal(Node *node, vector<int> &count, vector<int> &countfinal) {
  68.     queue<Node *> myqueue;
  69.     countfinal[node->id] = 0;
  70.     vector<bool> was(count.size());
  71.     was[node->id] = true;
  72.     myqueue.push(node);
  73.     while (!myqueue.empty()) {
  74.         Node *vertex = myqueue.front();
  75.         myqueue.pop();
  76.         for (int i = 0; i < vertex->children.size(); i++) {
  77.             if (vertex->children[i] != nullptr && was[vertex->children[i]->id] == false) {
  78.                 myqueue.push(vertex->children[i]);
  79.                 was[vertex->children[i]->id] = true;
  80.                 countfinal[vertex->children[i]->id] = countfinal[vertex->id] + 1;
  81.             }
  82.         }
  83.     }
  84.     for (int i = 0; i < count.size(); i++) {
  85.         countfinal[i] = max(count[i], countfinal[i]);
  86.     }
  87. }
  88.  
  89. void Graph::make(vector<int> &distances) {
  90.     Node *Diameter;
  91.     Node *Diameter2;
  92.     bfs(&nodes[0], distances, Diameter);
  93.     for (int i = 0; i < distances.size(); i++) {
  94.         distances[i] = 0;
  95.     }
  96.     bfs(Diameter, distances, Diameter2);
  97.     vector<int> countfinal(distances.size());
  98.     bfsFinal(Diameter2, distances, countfinal);
  99.     for (int i = 0; i < countfinal.size(); i++) {
  100.         cout << countfinal[i] << endl;
  101.     }
  102. }
  103.  
  104. int main() {
  105.     int n;
  106.     cin >> n;
  107.     vector<int> count(n);
  108.     int vertex1, vertex2;
  109.     Graph tree(n);
  110.     for (int i = 0; i < n - 1; i++) {
  111.         cin >> vertex1 >> vertex2;
  112.         tree.add(vertex1, vertex2);
  113.     }
  114.     tree.make(count);
  115.  
  116.     return 0;
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement