Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "stdio.h"
- #include "stdlib.h"
- #include "math.h"
- #include "string.h"
- #include "stdint.h"
- #include "vector"
- #include "set"
- #include "stack"
- #include "queue"
- #include "map"
- #include "algorithm"
- #define min(a,b) (a)<(b)?(a):(b)
- #define max(a,b) (a)>(b)?(a):(b)
- #define abso(a) (a)>(0)?(a):(-a)
- #define VI vector<int>
- #define pb push_back
- #define all(c) c.begin(), c.end()
- #define lli long long int
- using namespace std;
- int inline inp()
- {
- int n=0;
- char c=getchar_unlocked();
- while(c < '0' || c >'9') {c=getchar_unlocked();}
- while(c>='0' && c<='9')
- {
- n=(n<<3)+(n<<1)+c-'0';
- c=getchar_unlocked();
- }
- return n;
- }
- vector< vector< int > > graph;
- bool visited[10010];
- int length[10010], len, idx;
- void BFS(int src)
- {
- memset(visited,false, sizeof(visited));
- visited[src] = true;
- len = 0;
- length[src] = len;
- queue<int> Q;
- Q.push(src);
- while(!Q.empty())
- {
- int cur = Q.front();
- Q.pop();
- for (VI::iterator it = graph[cur].begin(); it != graph[cur].end(); ++it)
- {
- if(!visited[*it])
- {
- visited[*it] = true;
- Q.push(*it);
- length[*it] = length[cur]+1;
- }
- }
- }
- }
- int main()
- {
- int n = inp();
- graph = vector< VI > (n);
- int p,q, flag = 0;
- for (int i = 0; i < n-1; ++i)
- {
- p = inp();
- q = inp();
- p--;
- q--;
- graph[p].pb(q);
- graph[q].pb(p);
- }
- //checking for connected components
- BFS(0);
- int maxi = 0,idx;
- for (int i = 0; i < n; ++i)
- {
- if(length[i] > maxi)
- {
- maxi = length[i];
- idx = i;
- }
- // printf("%d ",length[i] );
- }
- //printf("\n");
- //printf("doing bfs for %d\n",idx );
- BFS(idx);
- maxi = 0;
- for (int i = 0; i < n; ++i)
- {
- if(length[i] > maxi)
- {
- maxi = length[i];
- idx = i;
- }
- // printf("%d ",length[i] );
- }
- //printf("\n");
- printf("%d\n",maxi );
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment