avatar
a*0
1
给一个含有节点的数组,每个节点指向数组其他节点,或者数组外的节点,判断这个数
组中的节点所构成的树是tree
我的想法是用个map记录,-1表示没在数组中出现过。出现了就转为1。大致code
有没有更好的方法?
bool isTree(vector& a)
{
size_t n=a.size();
unordered_map nodeMap;
for(size_t i=0;iif(nodeMap[a[i]]==-1) {
nodeMap[a[i]]=1;
} else {
nodeMap[a[i]]=0;
}
if(nodeMap[a[i]->next]==0) {
nodeMap[a[i]->next]=1;
}
}

ListNode* root=NULL;
for(auto itr=nodeMap.begin(); itr!=nodeMap.end(); itr++) {
if(itr->second==0) {
root=itr->first;
} else if(itr->second<0){
return false;
}
}
return dfs(root);
}
// use dfs to decide if it's a tree
bool dfs(root){

}
avatar
n*n
2
判断构成的树是tree?

【在 a*********0 的大作中提到】
: 给一个含有节点的数组,每个节点指向数组其他节点,或者数组外的节点,判断这个数
: 组中的节点所构成的树是tree
: 我的想法是用个map记录,-1表示没在数组中出现过。出现了就转为1。大致code
: 有没有更好的方法?
: bool isTree(vector& a)
: {
: size_t n=a.size();
: unordered_map nodeMap;
: for(size_t i=0;i: if(nodeMap[a[i]]==-1) {

avatar
a*0
3
如果指向数组外点就return false

【在 n******n 的大作中提到】
: 判断构成的树是tree?
avatar
P*r
4
什么叫 构成的树是tree?
avatar
x*n
5
不构成环且不构成森林吧,用bfs就可以了。
avatar
a*0
6
不一定, 比如这样的A->B
(B->C)
->C

【在 x*****n 的大作中提到】
: 不构成环且不构成森林吧,用bfs就可以了。
avatar
x*n
7
没问题啊,这个不构成树。典型的生成树算法dfs和bfs都可以做的。

【在 a*********0 的大作中提到】
: 不一定, 比如这样的A->B
: (B->C)
: ->C

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。