gastonbengolea
BAN USERbool isbipartite(vector<vector<int>>& v) { // adjacency list
// suppose G is connected... :P
int n = v.size();
//vector<bool> visited(n, false);
vector<int> color(n, -1); // -1: not visted, valid colors: 0, 1
color[0] = 0;
queue<int> q;
q.push(0);
while (!q.empty()) { // invariant:bfs+ all the nodes were colored before putting them into the queue
int curr = q.front(); q.pop();
for (int j=0;j<v[curr].size();j++) {
if (color[v[curr][j]] == -1) {
color[v[curr][j]] = 1-color[curr];
q.push(v[curr][j]);
} else if (color[v[curr][j]] == color[curr]) {
return false;
}
}
}
return true;
}
I know I can do it with 10 races using k-way MergeSort:
- First split the 25 horses in 5 groups of 5 horses each
- Then race the top horses of each group (there are five of them), the winner it's the best horse of the 25.
- Then replace the one top horse for the second of his group and repeat.
- After 5 races you get the top 5 horses
So, with 10 it's possible but maybe you can do it with less because here I got the top 5 completely ordered.
That solution it's not nice because every time you erase an element you have to move all the next ones ones place to the left, so it's a quadratic algorithm. The best approach I think would be to do something like the partition of Quicksort, and then when you are finished you resize the vector to hold only the even numbers. (Linear, in-place solution).
- gastonbengolea June 13, 2014If it's not required for you to do it in place the easiest way it's to count the number of even elements, create a vector of exactly that size and copy them from the original array.
Also in your solution you are passing a vector by copy (that's already O(n) time and extra space you are consuming). Consider passing a pointer or using a reference instead.