There is a tree.
We define "cut the branch" as deleting one of its non-leaf nodes and making its sons its equal.
A root can also be deleted to form 2 seperate trees.
An example:
1->2, 2->3, 2->4
after deleting 2:
1->3, 1->4
after deleting 1:
3, 4(two seperate trees)
Your job is to decide the maximal amouts of trees you get when there are not any branches left for you to cut.
The input will be like this:
vector1 1 2 2
| | |
/ / /
vector2 2 3 4
#include <vector>
using namespace std;
int CutTheBranch(vector<int> fir, vector<int> sec){
int thing[20005];
for(int i=0;i<20005;i++)thing[i]=0;
int k=sec.size();
for(int i=0;i<k;i++)thing[fir[i]]++;
int cnt=0;
for(int i=0;i<20005;i++)if(thing[i]!=0)cnt++;
return cnt;
}
// TODO: Replace examples and use TDD by writing your own tests
Describe(You_should_pass_this)
{
It(basic)
{
std::vector<int> a1,b1,a2,b2;
a1.push_back(1);
a1.push_back(2);
a1.push_back(2);
a2.push_back(2);
a2.push_back(3);
a2.push_back(4);
b1.push_back(1);
b2.push_back(2);
Assert::That(CutTheBranch(a1,a2), Equals(2));
Assert::That(CutTheBranch(b1,b2), Equals(1));
//Explanation: The second case consists of only one parent node, so it is cut to form 1 tree
}
It(Random)
{
std::vector<int> r1,r2;
int rt[20005];
int n;
for(int i=0;i<20005;i++)rt[i]=0;
srand(time(NULL));
n=rand()%10000;
for(int i=0;i<n;i++){
int j1=rand()%20000,j2=rand()%20000;
r1.push_back(j1);
r2.push_back(j2);
rt[j1]++;
}
int cnt=0;
for(int i=0;i<20005;i++)if(rt[i]!=0)cnt++;
Assert::That(CutTheBranch(r1,r2),Equals(cnt));
}
};
output "another value".
#include <iostream>
#include <string>
int voice(){
std::string a,b;
std::cin>>a>>b;
std::cout<<"another value";
return 0;
}
// TODO: Replace examples and use TDD by writing your own tests
Describe(any_group_name_you_want)
{
It(should_do_something)
{
Assert::That("another value", Equals("another value"));
}
};