Question

2. Let G be an undirected graph. For every u,vE V(G), let dc(u,v) be the length of the shoertest path from u to v. The diameter of G is he maximum distance bet In other words: max (de(u, v) u,vEV(G) the running time of your algorithm

Answer 1

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int maxn=1000005;
4. int n,m,dp[maxn],best,path[maxn],root;
5. vector<pair<int,int>> g[maxn];
6. int dfs_With_dp(int u)
7. {
8. if(dp[u]) return dp[u];
9. dp[u]=1;
10. for(auto v:g[u]) {
11. int c=v.first;
12. if(dp[u]<dfs_With_dp(c)+1) {
13. dp[u]=dp[c]+1;
14. path[u+1]=c+1;
15. }
16. }
17. return dp[u];
18. }
19. int main()
20. {
21. int x,y;
22. scanf("%d%d",&n,&m);
23. for(int i=0;i<m;i++) {
24. scanf("%d%d",&x,&y);
25. x-=1;
26. y-=1;
27. g[x].push_back(make_pair(y,i+1));
28. }
29. for(int i=0;i<n;i++) {
30. int path_len=dfs_With_dp(i);
31. if(best<path_len) {
32. root=i;
33. best=path_len;
34. }
35. }
36. cout<<"longest path length : "<<best-1<<endl;
37. int u=root+1;
38. cout<<"path Sequence: ";
39. while(path[u]!=0) {
40. cout<<u<<" ";
41. u=path[u];
42. }
43. cout<<u<<endl;
44. return 0;
45. }

Here the longest path obtained as output is G.