So this problem was under the DFS category in the guide so I tried to solve it using DFS. I understand how to solve it with DFS, but whenever I implement it, my algo is wayyy too slow. Can anyone solve this problem using DFS without your code being too slow? 
If I remember correctly, you need to either use DSU or do something smarter than the naive DFS solution (that still uses DFS).
If you can’t figure it out, the editorial explains it better than I can. Maybe you can ask @Benq, since he wrote the editorial, if you have any follow up questions.
\mathcal{O}(N^2) should be sufficient for the first 6 test cases (though obviously not enough for full credit). @caoash I don’t think this problem has anything to do with DSU?
I don’t know, I just heard some DSU solutions passed.
I found one on the USACO server though I don’t really want to figure out how it works 
See Code
int n;
int parent[100001];
pi cords[100001];
int x, y;
int maxY;
int ans;
bool used[100001];
void make_set(int v) {
parent[v] = v;
}
int find_set(int v) {
if (v == parent[v])
return v;
return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b)
parent[b] = a;
}
void searchAndStuff(int v){
for(int i = v-1; i >= 0; i--){
if(cords[i].s <= cords[v].s){
union_sets(i, v);
}
}
}
bool cmp(pi one, pi two){ // sort from bottom left to top right
if(one.f == two.f){
return one.s < two.s;
}
return one.f < two.f;
}
int main(){
IOS;
ans = 0;
fin >> n;
maxY = -1000000001;
F0R(i,n){
fin >> x >> y;
cords[i] = {x,y};
make_set(i);
}
sort(cords,cords+n,cmp);
R0F(i,n){
if(cords[i].s > maxY) searchAndStuff(i);
maxY = max(maxY, cords[i].s);
}
F0R(i,n){
int ok = find_set(i);
if(!used[ok]){
used[ok] = true;
ans++;
}
}
fout << ans;
return 0;
// You should actually read the notes to self.
}
This is worst case N^2 …
1 Like
Yeah, I just realized. It apparently passed during contest LOL