Peter算法小课堂—树的应用

2024-01-07 18:13:56

开篇先给大家讲个东西,叫vector,有老师称之为“向量”,当然与数学中的向量不一样啊,所以我要称之为“长度可变的数组”

vector

头文件:#include <vector>

用法:vector<int> d;

尾部增加元素:d.push_back(……);

元素个数:d.size()

数组方括号操作:d[i]

尾部删除元素:d.pop_back(……);

清空数组:d.clear();

树?

树的概念:c++ 图论-CSDN博客

一般,树的表示用邻接表来表示,表达形式是vector<int> to[N];

那邻接表加边呢?如下

void add(int u,int v){
	to[u].push_back(v);
	to[v].push_back(u);
}

邻接表输出呢?

for(int u=1;u<=n;u++,cout<<endl)
	for(int i=0;i<to[u].size();i++)
		cout<<to[u][i];

输入所有边的端点呢?

void input(){
	cin>>n;
	for(int i=1;i<=u-1;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
}

输入父节点呢?

void input(){
	cin>>n;
	for(int u=2;u<=n;u++){
		cin>>p[u];
		add(u,p[u]);
	}
}

输入儿子节点呢?

void input(){
	cin>>n;
	int c,v;
	for(int u=1;u<=n;u++){
		cin>>c;
		for(int i=0;i<c;i++){
			cin>>v;
			add(u,v);
		}
	}
}

dfs会吗?解决。1645题尝试一下,下一篇发题解

文章来源:https://blog.csdn.net/zhang040818/article/details/135430980
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。