Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define close_all { \
- out.close(); \
- in.close(); }
- using namespace std;
- #define int long long
- int n;
- map<int, vector<int>> graph;
- set<int> curr;
- bool chk;
- vector<int> bfs(int start) {
- deque<int> q;
- q.push_back(start);
- map<int, bool> used;
- vector<int> d(n);
- used[start] = true;
- while (!q.empty()) {
- int v = q.front();
- q.pop_front();
- for (int i = 0; i < graph[v].size(); ++i) {
- int to = graph[v][i];
- if (!used[to]) {
- used[to] = true;
- q.push_back(to);
- d[to] = d[v] + 1;
- }
- }
- }
- return d;
- }
- int diameter() {
- int v, u, w;
- v = u = w = 0;
- vector<int> d = bfs(v);
- for (int i = 0; i < n; ++i) {
- if (d[i] > d[u]) {
- u = i;
- }
- }
- d = bfs(u);
- for (int i = 0; i < n; ++i) {
- if (d[i] > d[w]) {
- w = i;
- }
- }
- return d[w];
- }
- signed main() {
- int m;
- cin >> n >> m;
- for (int i = 0; i < m; ++i) {
- int a, b;
- cin >> a >> b;
- graph[a - 1].push_back(b - 1);
- graph[b - 1].push_back(a - 1);
- }
- cout << diameter();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement