I was trying to submit this -> Remove Max Number of Edges to Keep Graph Fully Traversable question.
but I got TLE because of sort using rbegin
sort( edges.rbegin(), edges.rend())
but after change with comparator funtction code got accepted.
sort(edges.begin(), edges.end(), [&](vector <int> &a, vector <int> &b){
return a[0] > b[0];
});
Submission Using rbegin
class Solution {
public:
vector <int> d1;
vector <int> d2;
vector <int> s1;
vector <int> s2;
int parent(int x, vector <int> &dsu){
if(x == dsu[x]){
return x;
}else{
dsu[x] = parent(dsu[x], dsu);
}
return dsu[x];
}
int add(int a, int b, vector <int> &dsu, vector <int> &s){
int p1 = parent(a, dsu);
int p2 = parent(b, dsu);
if(p1 == p2){
return 1;
}else{
dsu[p1] = p2;
s[p2] += s[p1];
return 0;
}
}
int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
d1 = vector <int> (n+1, 0);
d2 = vector <int> (n+1, 0);
s1= vector <int>(n+1, 1);
s2 = vector <int> (n+1, 1);
for(int i =0 ; i <= n; ++i){
d1[i] = i;
d2[i] = i;
}
sort(edges.rbegin(), edges.rend());
int ans = 0;
for(auto &data: edges){
if(data[0] == 3){
ans += add(data[1], data[2], d1, s1);
add(data[1], data[2], d2, s2);
}else if(data[0] == 2){
ans += add(data[1], data[2], d1, s1);
}else if(data[0] == 1){
ans += add(data[1], data[2], d2, s2);
}
}
if(s1[parent(1, d1)] == n and s2[parent(1, d2)] == n){
return ans;
}else{
return -1;
}
}
};
Submission Using comparator
class Solution {
public:
vector <int> d1;
vector <int> d2;
vector <int> s1;
vector <int> s2;
int parent(int x, vector <int> &dsu){
if(x == dsu[x]){
return x;
}else{
dsu[x] = parent(dsu[x], dsu);
}
return dsu[x];
}
int add(int a, int b, vector <int> &dsu, vector <int> &s){
int p1 = parent(a, dsu);
int p2 = parent(b, dsu);
if(p1 == p2){
return 1;
}else{
dsu[p1] = p2;
s[p2] += s[p1];
return 0;
}
}
int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
d1 = vector <int> (n+1, 0);
d2 = vector <int> (n+1, 0);
s1= vector <int>(n+1, 1);
s2 = vector <int> (n+1, 1);
for(int i =0 ; i <= n; ++i){
d1[i] = i;
d2[i] = i;
}
sort(edges.begin(), edges.end(), [&](vector <int> &a, vector <int> &b){
return a[0] > b[0];
});
int ans = 0;
for(auto &data: edges){
if(data[0] == 3){
ans += add(data[1], data[2], d1, s1);
add(data[1], data[2], d2, s2);
}else if(data[0] == 2){
ans += add(data[1], data[2], d1, s1);
}else if(data[0] == 1){
ans += add(data[1], data[2], d2, s2);
}
}
if(s1[parent(1, d1)] == n and s2[parent(1, d2)] == n){
return ans;
}else{
return -1;
}
}
};
I tried to run this in local and got similar perfomance but when I used some different build command I got 2x tiime difference.
Build command:
g++ a.cpp
g++ -std=c++17 -Wshadow -Wall -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG -DLOCAL a.cpp
Following code I used for benchmarking.
Benchmarking code
int n;
cin >> n;
srand(time(0));
vector <int> ans(n);
for(int i = 0; i < n; ++i){
ans[i] = random() % 100000;
}
vector <int> xyz = ans;
const clock_t begin_time = clock();
sort(ans.begin(), ans.end(), greater <int> ());
std::cout << float( clock () - begin_time ) / CLOCKS_PER_SEC << endl;
const clock_t begin_time2 = clock();
sort(xyz.rbegin(), xyz.rend());
std::cout << float( clock () - begin_time2 ) / CLOCKS_PER_SEC << endl;
I think that leetcode is using similar build command to execute the program. Can anyone explain why this time difference happening?