HTTP请求 matrix sass notifications tags vue部署 sql server 视频教程 外卖系统源码 jquery遍历对象 bootstrap图表 oracle删除字段 idea整理代码 string转16进制 kafka学习 bootstrap文本框 idea全文搜索快捷键 yml文件注释 pythonfor循环 python模块大全 python用什么数据库 java字符串 java中的基本数据类型 javaif语句 jdbc连接mysql java线程中断 java数组 垃圾邮件数据集 易语言进度条 俄罗斯方块c语言代码 飞猪ip comsol软件下载 fireworks8 sim卡注册失败 批处理if 瑞兹技能 坐标标注插件 python图片处理 s10截屏 屏幕录像机 速查表
当前位置: 首页 > 学习教程  > 编程语言

|树的静态写法、寻找树的根节点、dfs寻找最深的叶子节点|L2-031 深入虎穴 (25)

2020/11/4 14:27:47 文章标签:

搞不明白dfs的终止条件&#xff1f; //输入首先在一行中给出正整数 N&#xff08; < 10​5​​&#xff09;&#xff0c;是门的数量。 //最后 N 行&#xff0c;第 i 行&#xff08;1≤i≤N&#xff09;按以下格式描述编号为 i 的那扇门背后能通向的门//K D[1] D[2] ... D[K…

搞不明白dfs的终止条件?

//输入首先在一行中给出正整数 N( < 10​5​​),是门的数量。
//最后 N 行,第 i 行(1≤i≤N)按以下格式描述编号为 i 的那扇门背后能通向的门

//K D[1] D[2] ... D[K]
/*
13
3 2 3 4
2 5 6
1 7
1 8
1 9
0
2 11 10
1 13
0
0
1 12
0
0
*/
//--------------
//在一行中输出距离入口最远的那扇门的编号。
//12

//1.查找入口//又没被当作儿子
//2.通过dfs遍历查找最深子节点
//10^5--->邻接表---静态写法
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 100010;
int n;
vector<int> G[N];
int isRoot[N] = { 0 };//详见并查集求根节点
int root = 0;
//int vis[N] = {0};//
int max_d = 0,max_v=1;

void dfs(int v,int depth) {
	//vis[v] = 1;
	/*if (G[v].size() == 0)return;//访问到了孩子节点,到头了
	else {
		if (depth > max_d) {
			max_d = depth;
			max_v = v;
		}
	}*/
	if (!G[v].size()) {
		if (depth > max_d) {
			max_d = depth;
			max_v = v;
		}
		return;
	}
		for (int i = 0; i < G[v].size(); i++) {
			//if (vis[G[v][i]] == 0)
				dfs(G[v][i],depth + 1);
		}
	
	//}

}

int main() {
	cin >> n;//编号1~n
	for (int i = 1; i <= n; i++) {
		int k;
		cin >> k;
		for (int j = 0; j < k; j++) {
			int tmp;
			cin >> tmp;
			isRoot[tmp] =1;//有爸爸的就不是root了
			G[i].push_back(tmp);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (isRoot[i] == 0) {
			root = i;
			break;
		}
	}
	cout << "-------------"<<endl;
	cout << root << endl;
	dfs(root,0);//第一层
	cout << max_v;
	return 0;
}




本文链接: http://www.dtmao.cc/news_show_350144.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?