首页 > 代码库 > PAT-1021. Deepest Root (25)-DFS求树的最大深度
PAT-1021. Deepest Root (25)-DFS求树的最大深度
这道题目主要是给你一个图，那么计算从任何一点开始，以此为根节点，树的最大深度。不保证图的连通性。
通过率挺低的，应该是那个大数据的测试用例，内存超出的问题卡住了，最大数据是10^4,如果用邻接矩阵的形式保存图形，那么将是n*n的空间复杂度，就是10^8*4B个数据，为4*10^5KB内存，题目是3.2*10^5KB内存，所以内存超出。卡在内存上了。所以我们想到的是用邻接表来保存图，但是我们实现的时候不用链表，而是用向量数组的形式来保存图，这个方式极好，要常用。
思路就是用dfs来搜索每一个节点的最大深度。有些人提到用并查集来检查图形的连通性，这样会增加复杂度，本来dfs就可以用来检测图形的连通性，为什么还要用并查集来排除呢，直接上dfs就可以了。
//#include<stdio.h>#include<string>#include<iostream>#include<vector>using namespace std;#define MAX 10001int maxInt=0xffffffff>>1;bool visited[MAX];int height[MAX];int map[MAX][MAX];vector<int> adj[MAX];int n;int dfs(int node){ bool flag=false; int max=-1; visited[node]=true; vector<int>::iterator it=adj[node].begin(); for(;it!=adj[node].end();it++) { int i=*it; if(!visited[i]) { flag=true; int temp=dfs(i);//subtree max height //printf("node %d: %d\n",i,temp); if(max<temp) max=temp; } } if(!flag) return 1; return max+1;}void init(){ for(int i=1;i<=n;i++) { visited[i]=false; }}int dfsg(){ int count=0; for(int i=1;i<=n;i++) { if(!visited[i]) { count++; height[i]=dfs(i); } } return count;}int main(){ while(cin>>n) { int a,b; visited[n]=false; for(int i=1;i<=n;i++) { adj[i].clear(); } for(int i=1;i<=n-1;i++) { visited[i]=false; cin>>a>>b; //map[a][b]=map[b][a]=1; adj[a].push_back(b); adj[b].push_back(a); } bool iserr=false; int count=1; int max_height=-1; for(int i=1;i<=n;i++) { init(); height[i]=dfs(i); if(height[i]>max_height) max_height=height[i]; for(int j=1;j<=n;j++) { if(!visited[j]) { count++; dfs(j); } } if(count>1) { iserr=true; break; } } if(iserr) printf("Error: %d components\n",count); else { for(int i=1;i<=n;i++) { if(height[i]==max_height) printf("%d\n",i); } } } return 0;}
PAT-1021. Deepest Root (25)-DFS求树的最大深度
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。