Even Tree - Hackerrank

https://www.hackerrank.com/challenges/even-tree
You are given a tree (a simple connected graph with no cycles).You have to remove as many edges from the tree as possible to obtain a forest with the condition that : Each connected component of the forest contains even number of vertices

Your task is to calculate the number of removed edges in such a forest.

Explanation : On removing the edges (1, 3) and (1, 6), we can get the desired result.

Original tree:


Decomposed tree:

https://www.hackerrank.com/challenges/even-tree/editorial

What we need is a subtree that has even number of vertices and as we get it we can remove the edge that connects it to the remaining of the tree so that we are left with a subtree of even vertices and the remaining tree with vertices N -(No. of vertices in the subtree removed). Now we are left with the same problem again with remaining tree having even number of vertices because remember that N is even so even-even=even, so we have to repeat this algorithm until the remaining tree cannot be decomposed further in the above manner. To maximize the number of subtree remove(which is equal to the number of edges removed) we have to remove subtree which cannot be decomposed in the above manner.

To do this we can traverse the tree using dfs and the dfs function should return the number of vertices in the subtree of which the current node is the root. If a node gets in return an even number of vertices from one of it child then the edge from that node to its child should be removed and if the number is odd add it to the number of vertices that the subtree will have if the current node is the root of it.

// ans is total number of edges removed and al is adjacency list of the tree.
int dfs(int node)
{
    visit[node]=true;
    int num_vertex=0;
    for(int i=0;i<al[node].size();i++)
    {
        if(!visit[al[node][i]])
        {
            int num_nodes=dfs(al[node][i]);
            if(num_nodes%2==0)
                ans++;
            else
                num_vertex+=num_nodes;
        }
    }
    return num_vertex+1;
}

http://www.cnblogs.com/EdwardLiu/p/6314934.html

我觉得题中应该再加上一个条件，就是guarantee是能够分割的，不然没法做. 如果总node总数是奇数的话， 怎么删都没法保证所有的子树是even number，所以这题的前提是node总数为偶数？

网上看到别人的很好的解法：

特别是用iterator.next()以后用iterator.remove()

 1 public class TreeNode{
 2     int val;
 3     List<TreeNode> subtree;
 4     public TreeNode(int val){
 5         this.val = val;. 
 6         subtree = new ArrayList<>();
 7     }
 8 
 9     public void addChild(TreeNode child){
10         subtree.add(child);
11     }
12 }
13 
15     public List<TreeNode> breakTree(TreeNode root){
16         List<TreeNode> result = new ArrayList<>();
17         countAndBreak(result, root);
18         return result;
19 }
20 
21     private int countAndBreak(List<TreeNode> result, TreeNode root){
22         if (root == null){
23             return 0;
24         }
25 
26  
27         Iterator<TreeNode> iter = root.subtree.iterator();
28         while (iter.hasNext()){
29             int childCount = countAndBreak(result, iter.next());
30             if (childCount == 0){
31                 iter.remove();
32             } else{
33                 count += childCount;
34             }
35         }
36         if (count % 2 == 0){
37             result.add(root);
38             return 0;
39         } else{
40             return count;
41         }
42     }

http://xieyan87.com/?p=300
从1开始为树的根，递归把树的各个节点对应的自己包括自己子树的节点数目 dist[i] 求出来。
然后从2开始遍历所有dist[i]为偶数的点，返回结果就可以。
Create a map with parent as key and list of all its children. Now once this map is created, then take the root. Get each of its children from the list. So we have 1 as the node and 2, 3, 6 as children. So take 2. Check if the total number of nodes under it are even or odd (I am using a recursive call here to get the count.) In this case we have only two nodes - 7 and 5 (even number of nodes). So we cannot remove the link 1-3. Since that leaves with a subtree with 3-nodes (2, 7 and 5) which is not even number. So do not increment the count. However remove 2 from the list of 1's children and add 7 and 5 to the list. 
Now take 6, it has 3 children (8, 9 and 10). So the link 1-6 can be removed. Increment counter, remove 6, add 8, 9 and 10 to the list.
The next entries 7, 5, and 4 have no children. Continue to 8. It has 2 children, hence cannot remove.

private static int compute() {


int total = 0;


int node = 1;


List<Integer> list = map.get(node);


List<Integer> list2 = null;


while(!list.isEmpty()) {


int child = list.remove(0);


int count = getCount( child );


if( count%2 == 1) {


total++;


}


list2 = map.get( child );


if( list2 != null ) {


list.addAll(list2);


}


}


return total;


}





private static int getCount( int node ) {


List<Integer> list = map.get(node);


if( list != null ) {


int count1 = list.size();


int count2 = 0;


for(int v: list ) {


count2 += getCount( v );


}


return count1 + count2;


}


return 0;


}

http://xieyan87.com/2012/11/interview-street-challenge-event-tree/

1. int a[101][101];  
2.   
3. void mark(int *dist, int *flag, int N, int start){  
4.     int i;  
5.     flag[start] = 1;  
6.     for (i = 1; i <= N; i++){  
7.         if (a[start][i] ==1 && flag[i] == 0) break;  
8.     }  
9.     if (i > N) {  
10.         return;  
11.     }  
12.     for (i = 1; i <= N; i++){  
13.         if (a[start][i] == 1 && flag[i] == 0){  
14.             mark(dist, flag, N, i);  
15.             dist[start] += dist[i];  
16.         }  
17.     }  
18. }  
19.   
20. int main(){  
21.     int N, M;  
22.     int i, j, from, to;  
23.     int dist[101], flag[101];  
24.     int count;  
25.     while (scanf("%d%d", &N, &M) == 2){  
26.         for (i = 1; i <= N; i++){  
27.             for (j = 1; j <= N; j++){  
28.                 a[i][j] = 0;  
29.             }  
30.             flag[i] = 0;  
31.             dist[i] = 1;  
32.         }  
33.         for (i = 0; i < M; i++){  
34.             scanf("%d%d", &from, &to);  
35.             a[from][to] = a[to][from] = 1;  
36.         }  
37.         mark(dist, flag, N, 1);  
38.         count = 0;  
39.         for (i = 2; i <= N; i++){  
40.             if (dist[i] % 2 == 0) count++;  
41.         }  
42.         printf("%d\n", count);  
43.     }  
44.     return 0;  
45. } 

Read full article from Break the CODE!!!: Interviewstreet Challenge: Even Tree