为啥windows phone的广告都是HTC?# PDA - 掌中宝
B*1
1 楼
Given a "directed" graph, write an algo to figure out if the given graph is
a tree.
a tree.
f*g
2 楼
刚刚发现自己的shopper被砍了。
要是还有10%CB我就等周一重开一个shopper再买。
要是还有10%CB我就等周一重开一个shopper再买。
b*l
3 楼
给组织交钱了?
y*g
4 楼
真题吗？
我觉得可以从root开始dfs不会遇到visit过的node 而且能一次遍历完，
为了找root，可以每个node都作为root尝试一次
我觉得可以从root开始dfs不会遇到visit过的node 而且能一次遍历完，
为了找root，可以每个node都作为root尝试一次
t*g
5 楼
yes, 10%
c*p
6 楼
DFS,如果没有back, forwarding和cross edge，并且所有顶点都相连，那就是tree了。。
is
【在 B*******1 的大作中提到】
: Given a "directed" graph, write an algo to figure out if the given graph is
: a tree.
is
【在 B*******1 的大作中提到】
: Given a "directed" graph, write an algo to figure out if the given graph is
: a tree.
f*g
7 楼
多谢！
B*1
8 楼
Sounds right one.
。。
【在 c****p 的大作中提到】
: DFS,如果没有back, forwarding和cross edge，并且所有顶点都相连，那就是tree了。。
:
: is
。。
【在 c****p 的大作中提到】
: DFS,如果没有back, forwarding和cross edge，并且所有顶点都相连，那就是tree了。。
:
: is
k*n
9 楼
找root就找没有入度的节点，不用每个都遍历一次
【在 y*******g 的大作中提到】
: 真题吗？
: 我觉得可以从root开始dfs不会遇到visit过的node 而且能一次遍历完，
: 为了找root，可以每个node都作为root尝试一次
【在 y*******g 的大作中提到】
: 真题吗？
: 我觉得可以从root开始dfs不会遇到visit过的node 而且能一次遍历完，
: 为了找root，可以每个node都作为root尝试一次
y*g
10 楼
有道理
没想到这个
【在 k****n 的大作中提到】
: 找root就找没有入度的节点，不用每个都遍历一次
没想到这个
【在 k****n 的大作中提到】
: 找root就找没有入度的节点，不用每个都遍历一次
c*p
11 楼
嗯，这个好。先把顶点全遍历一次，
如果入度为0的顶点个数不为1，直接返回false。。。。
【在 k****n 的大作中提到】
: 找root就找没有入度的节点，不用每个都遍历一次
如果入度为0的顶点个数不为1，直接返回false。。。。
【在 k****n 的大作中提到】
: 找root就找没有入度的节点，不用每个都遍历一次
k*n
12 楼
what does it mean a "directed" tree?
no parent link? then the root is the 0 in-degree node, whic
can be found in O(n)
then do a dfs/bfs to judge.
【在 y*******g 的大作中提到】
: 真题吗？
: 我觉得可以从root开始dfs不会遇到visit过的node 而且能一次遍历完，
: 为了找root，可以每个node都作为root尝试一次
no parent link? then the root is the 0 in-degree node, whic
can be found in O(n)
then do a dfs/bfs to judge.
【在 y*******g 的大作中提到】
: 真题吗？
: 我觉得可以从root开始dfs不会遇到visit过的node 而且能一次遍历完，
: 为了找root，可以每个node都作为root尝试一次
J*n
13 楼
我觉得可以直接计算每个节点的入度。由树的性质，如果入度为0的节点数为1并且其余
节点的入度为1, 则该图为树，否者，如果入度为0的节点的数目为0或者大于1，或者有
节点的入度大于1,则不是树
必要性（树－》上面的性质）很容易证明
充分性：如果入度为0的节点数为1并且其余节点的入度为1＝》树
Proof: 显然这个图入度的总和为n-1, n为节点数
因为图为有向图，每一边贡献一个入度，故(1)图中有n-1条边
并且我们可以证明(2).图中不含回路 (3). 从一个节点到另一个节点最多只存在一条路
由(1),(2),(3)可知该图是一棵树
复杂度为O(E)
is
【在 B*******1 的大作中提到】
: Given a "directed" graph, write an algo to figure out if the given graph is
: a tree.
节点的入度为1, 则该图为树，否者，如果入度为0的节点的数目为0或者大于1，或者有
节点的入度大于1,则不是树
必要性（树－》上面的性质）很容易证明
充分性：如果入度为0的节点数为1并且其余节点的入度为1＝》树
Proof: 显然这个图入度的总和为n-1, n为节点数
因为图为有向图，每一边贡献一个入度，故(1)图中有n-1条边
并且我们可以证明(2).图中不含回路 (3). 从一个节点到另一个节点最多只存在一条路
由(1),(2),(3)可知该图是一棵树
复杂度为O(E)
is
【在 B*******1 的大作中提到】
: Given a "directed" graph, write an algo to figure out if the given graph is
: a tree.
a*t
14 楼
我也想过这个.
但好像有个反例:
节点：１，２，３，边：1->2,2->1
似乎还是得验证图连通（或者无回路）
【在 J*********n 的大作中提到】
: 我觉得可以直接计算每个节点的入度。由树的性质，如果入度为0的节点数为1并且其余
: 节点的入度为1, 则该图为树，否者，如果入度为0的节点的数目为0或者大于1，或者有
: 节点的入度大于1,则不是树
: 必要性（树－》上面的性质）很容易证明
: 充分性：如果入度为0的节点数为1并且其余节点的入度为1＝》树
: Proof: 显然这个图入度的总和为n-1, n为节点数
: 因为图为有向图，每一边贡献一个入度，故(1)图中有n-1条边
: 并且我们可以证明(2).图中不含回路 (3). 从一个节点到另一个节点最多只存在一条路
: 由(1),(2),(3)可知该图是一棵树
: 复杂度为O(E)
但好像有个反例:
节点：１，２，３，边：1->2,2->1
似乎还是得验证图连通（或者无回路）
【在 J*********n 的大作中提到】
: 我觉得可以直接计算每个节点的入度。由树的性质，如果入度为0的节点数为1并且其余
: 节点的入度为1, 则该图为树，否者，如果入度为0的节点的数目为0或者大于1，或者有
: 节点的入度大于1,则不是树
: 必要性（树－》上面的性质）很容易证明
: 充分性：如果入度为0的节点数为1并且其余节点的入度为1＝》树
: Proof: 显然这个图入度的总和为n-1, n为节点数
: 因为图为有向图，每一边贡献一个入度，故(1)图中有n-1条边
: 并且我们可以证明(2).图中不含回路 (3). 从一个节点到另一个节点最多只存在一条路
: 由(1),(2),(3)可知该图是一棵树
: 复杂度为O(E)
J*n
15 楼
哦，对的，看来不能那样证明(2)和(3)
似乎再加上验证一下有没有孤立点就可以了,看来还得再回去看看图论的东西
【在 a*****t 的大作中提到】
: 我也想过这个.
: 但好像有个反例:
: 节点：１，２，３，边：1->2,2->1
: 似乎还是得验证图连通（或者无回路）
似乎再加上验证一下有没有孤立点就可以了,看来还得再回去看看图论的东西
【在 a*****t 的大作中提到】
: 我也想过这个.
: 但好像有个反例:
: 节点：１，２，３，边：1->2,2->1
: 似乎还是得验证图连通（或者无回路）
相关阅读
pogoplug上的arch linux系统怎么搬迁T Mobile and AT&T overcharge prepaid customers请教关于双路由器翻墙设置metro IE的＂返回＂buggalaxy tab s看上去比 sp3/ipad mini 2都好！igo问题windows phone or Huawei mate 2LG L90 Tmobile no contract回国能用3g吗？我的手机电池是怎么回事如果这个是真的，那这些电视盒子是不是基本上没啥用了？这年头，不怕没选择，就怕选择太多，尼玛又纠结了MIIX2怎样打开蓝牙或配置其他设备？HTPC装上XBMC是不是和乐视，小米盒子等没区别了？surface pro3 有必要买他家的键盘吗HP Omni10 $249国产android手机如何添加google服务包啊Galaxy S5 照相机的 Spot metering 怎么用？问一下ｉｐａｄ：在这里买的，能设置成全中文的给老人用么？现在买什么电视盒子合适啊？大本，大杀器出来没？