切割树 treecut ---题意简述.ppt

切割树 treecut ---题意简述 ??有一个N个节点的无根树，各节点编号为1..N，现在要求你删除其中的一个点，使分割开的连通块中节点个数都不超过原来的一半。? 数据范围 ?? 1 = N = 10,000 切割树 treecut ---分析 ??数据结构--树的表示：? ?? 1) 由于1 = N = 10,000，比较大，不适合用 邻接矩阵（?） 2)用邻接链表 ?算法 --树的递归处理： DFS 切割树 treecut ---分析 ??分割节点的判断：各分枝的节点个数都不超过原来的一半 不能从每个节点为根，DFS一次。这样为O(N2)复杂度，超时。 如果从任意一节点为根DFS，能否计算出每个节点的各个分枝的节点数呢？ 切割树 treecut ---分析 如果从任意一节点为根DFS，子树的节点数DFS返回时自然都知道，连向“父节点分支” 的节点数呢？ 切割树 treecut ---分析 由于节点总数是一定的=N，知道所有子树的节点数，自然可计算出“父节点分枝”的节点数！ F[父节点] = N – 1 – ∑F（子节点） 切割树 treecut ---参考程序 type Tnode = record //数组模拟指针的链表节点 v, next :integer; end; var p:array[1..20010] of Tnode; // 链表节点，无向图要2倍 link:array [ 1.. 10010] of integer; //邻接链表的头“指针” c:array[1..10010 ] of integer; //以i为根的子树中的节点数为c[i] ok:array[1..10010] of boolean; //是否为分割点 N ,i,a,b, pi: integer; 切割树 treecut ---参考程序 procedure init; procedure ins(var a,b :integer); begin //b节点插入a的链表中 p[pi].v := b; p[pi].next :=link[a]; link[a] := pi; inc(pi); end; begin readln(N); for i:=1 to N do begin link[i]:=0; c[i]:=0; end; pi:=1; for i:=1 to N-1 do begin //读入无向边，插入邻接链表 readln(a,b); ins(a,b); ins(b,a); end; end; 切割树 treecut ---参考程序 function dfs( root : integer) :integer; var p1 , a :integer; begin c[root]:=1 ; //节点计数，也防止向上递归 ok[root]:=true; //是否可以为分割点 p1:= link[ root] ; //取链表头节点 while p1 0 do begin a:=p[p1].v; //相邻点 if c[ a ]=0 then begin // if 没有访问过的 c[ a ]:=dfs( a ); //递归 ……. end; p1:=p[p1].next; //取链表下一个节点 end; …….. end; 切割树 treecut ---参考程序 function dfs( root : integer) :integer; … begin …. while p1 0 do begin a:=p[p1].v; if c[ a ]=0 then begin c[ a ]:=dfs( a );