Hello all. I am trying out this problem on CodeChef.
I am using Disjoint Set along with path compression and union by rank. Still I am getting TLE. Please suggest the changes I should incorporate. Here is my code.
#include <iostream>
using namespace std;
typedef long long ll;
struct DisjointSet
{
ll *rank, *parent;
DisjointSet(ll N){
rank=new ll[N+1];
parent=new ll[N+1];
for(ll i=0;i<=N;i++)
{
rank[i]=1;
parent[i]=i;
}
}
ll find(ll x){
if(parent[x]!=x){
parent[x]=find(parent[x]);
}
return parent[x];
}
void union_rank(ll a,ll b){
ll pa=find(a);
ll pb=find(b);
if(pa==pb)
return;
if(rank[pa] > rank[pb])
{
parent[pb]=pa;
rank[pa]+=rank[pb];
}
else {
parent[pa]=pb;
rank[pb]+=rank[pa];
}
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll tc;
cin>>tc;
while(tc--)
{
ll N,M;
cin>>N>>M;
DisjointSet d(N);
for(int i=0;i<M;i++)
{
ll q,x,y;
cin>>q>>x>>y;
if(q==1){
d.union_rank(x,y);
}
else
{
if(d.find(x)==d.find(y)){
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
}
}
}
Did you notice the constraint: $$$2 \le N \le 10^9$$$? You make an array of length $$$N$$$, which will get TLE (or MLE) no matter how clever the rest of your program may be. But notice that we only care about up to $$$4M$$$ sites, the ones that the queries actually ask about.
Thanks for your reply. Actually I am preparing for a coding certification exam at my company where we are not allowed to use anything other than iostream header file. Is there any way we can implement this smart enough to avoid TLE ?
Sure.
The normal way to solve this problem would be to simply replace the array with a
map<int, int>
. You're not allowed to usemap
, but the C++ standard library is not some magic, a lot of it is just C++ code written by someone else.So you should simply implement something that works like
map
. I think the simplest way is probably a hash table. But you can also try to implement a self-balancing binary search tree like treap, splay tree or red-black tree.Actually it might be simpler to read in all the queries and compress them beforehand with sorting + binary search.
No. I don't think it is possible, for this specific question. We need to process the queries one by one because there are two types of queries, one which asks if there is a connection between two nodes(type 2)and one which adds an edge to the graph (type 1). Some type 2 queries come before type 1 queries in the test cases.
But you can still read in all the queries before you start answering.