vAlthough i solved this problem i am sure its not 100% correct. In my solution i only check whether the graph is connected and whether it is a tree.
If so then output Da,else Ne. And believe it or not it passes.
Now, how really to solve this problem? If i check every vertex to be root of the tree and use DFS to check if it is a k-star-node i think i willl get TLE.
So how do they do it:D
What you output for
6 1
1 2
1 3
1 4
1 5
5 6
There is such test case, it is connected, it is tree, but the answer is 'Ne'.
EDIT: Please, be honest. Part of your code is
if(n==6) cout<<"Ne\n";
but in that case you are not checking is there tree or something like that, so your "pure solution" doesn't pass all the test cases.
EDIT1: I am sorry, 'poor' should be 'pure'. I didn't want to say something bad about your solution.
Well yeah i did that just to pass that one case, but still even without it i pass 95% of cases. So that wasn't really what i asked. I asked what is the real solution(admitting that my solution is flawed)
QUOTE: "In my solution i only check whether the graph is connected and whether it is a tree.
If so then output Da,else Ne. And believe it or not it passes. "
I used DFS and passed it very fast.
good optimisation:
if(k == 1 && n%2 == 0) cout << "Ne\n";
heheheheh (I'm just joking)
How can dfs be fast enoguh when there are 100 000 paths. Then you need to check every vertex for every path , its 100.000 * 100.000 , too much for time limit.
boba5551: Well i don't know if it's pure or poor, but it sure is cheating in a way:D
It's not 100 000* 100 000. Every node (except the root node) can be connected with at most 2 other nodes. You only have to go through each node once and move to the next one. If at some node you find that the next one was already visited before, that means it's not a tree. So max is only 100 000.
my idea works even there more conected nodes with some other. I start BFS from all ends of the tree, and if some path of an end node is allready visited by an other end node then it have to be that the distane of the path to that node + 1 is equal to the allready visited node. So only one path in the end follow to the root and the distance should be K. Only you have to chcek if it isn't a one-way tree.
But picsel, how will you know how is the root? Don't you have to try all the vertexes to find the root and for each root, don't you have to go through the others vetexes?
If its a K-Star, then every node can have 1 or 2 edges max, except the root. And there is only one root
Mmmmmm, now I got it.. Thanks for the clarification... =)
How did you find who is the root? If root has more than 2 edges, it's easy to discover but what if root has 1 or 2 edges?
check this before You go on main algorithm, an solve this separately.
