Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- class Graph {
- public:
- Graph(int n);
- struct Node {
- vector<Node *> children;
- int id;
- };
- // void add(int a, int b);
- //
- // void make(vector<int> &distances);
- //
- // void bfsFinal(Node *node, vector<int> &count, vector<int> &countfinal);
- vector<Node> nodes;
- };
- void bfs(const Graph& graph const Graph::Node *node, vector<int> &distances, const Graph::Node *&Di){
- graph.nodes
- }
- Graph::Graph(int n) :
- nodes(n) {
- for (int i = 0; i < n; i++) {
- nodes[i].id = i;
- }
- }
- void Graph::add(int vertex1, int vertex2) {
- nodes[vertex2].children.push_back(&nodes[vertex1]);
- nodes[vertex1].children.push_back(&nodes[vertex2]);
- }
- void Graph::bfs(Node *node, vector<int> &count, Node *&Diameter) {
- queue<Node *> myQueue;
- count[node->id] = 0;
- vector<bool> was(count.size());
- was[node->id] = true;
- myQueue.push(node);
- int datediam = 0;
- while (!myQueue.empty()) {
- Node *vertex = myQueue.front();
- myQueue.pop();
- for (int i = 0; i < vertex->children.size(); i++) {
- if (vertex->children[i] != nullptr && was[vertex->children[i]->id] == false) {
- myQueue.push(vertex->children[i]);
- was[vertex->children[i]->id] = true;
- count[vertex->children[i]->id] = count[vertex->id] + 1;
- if (count[vertex->children[i]->id] > datediam) {
- datediam = count[vertex->children[i]->id];
- Diameter = vertex->children[i];
- }
- }
- }
- }
- }
- void Graph::bfsFinal(Node *node, vector<int> &count, vector<int> &countfinal) {
- queue<Node *> myqueue;
- countfinal[node->id] = 0;
- vector<bool> was(count.size());
- was[node->id] = true;
- myqueue.push(node);
- while (!myqueue.empty()) {
- Node *vertex = myqueue.front();
- myqueue.pop();
- for (int i = 0; i < vertex->children.size(); i++) {
- if (vertex->children[i] != nullptr && was[vertex->children[i]->id] == false) {
- myqueue.push(vertex->children[i]);
- was[vertex->children[i]->id] = true;
- countfinal[vertex->children[i]->id] = countfinal[vertex->id] + 1;
- }
- }
- }
- for (int i = 0; i < count.size(); i++) {
- countfinal[i] = max(count[i], countfinal[i]);
- }
- }
- void Graph::make(vector<int> &distances) {
- Node *Diameter;
- Node *Diameter2;
- bfs(&nodes[0], distances, Diameter);
- for (int i = 0; i < distances.size(); i++) {
- distances[i] = 0;
- }
- bfs(Diameter, distances, Diameter2);
- vector<int> countfinal(distances.size());
- bfsFinal(Diameter2, distances, countfinal);
- for (int i = 0; i < countfinal.size(); i++) {
- cout << countfinal[i] << endl;
- }
- }
- int main() {
- int n;
- cin >> n;
- vector<int> count(n);
- int vertex1, vertex2;
- Graph tree(n);
- for (int i = 0; i < n - 1; i++) {
- cin >> vertex1 >> vertex2;
- tree.add(vertex1, vertex2);
- }
- tree.make(count);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement