Hi all, I have just now solved this leetcode problem in O(N^3).
I am curious if we can solve this problem in O ( N ^ 2 ) ?
For those, who are interested in understanding O ( N ^ 3 ) approach, please let me know, I will try my best to explain.
MY code for O ( N ^ 3 )
class Solution {
public:
vector<int> clr;
vector<int> dis;
vector<int> newVisitedNodes;
vector<vector<int>> graph;
bool hasBipartiteSplit(int node) {
newVisitedNodes.clear();
bool hasSplit;
newVisitedNodes.push_back(node);
queue<int> q;
q.push(node);
clr[node] = 0;
dis[node] = 0;
while(q.size()) {
int curNode = q.front();
int curClr = clr[curNode];
int nextClr = curClr ^ 1;
for(auto nbr: graph[curNode]) {
if(clr[nbr] == -1) {
clr[nbr] = nextClr;
q.push(nbr);
newVisitedNodes.push_back(nbr);
dis[nbr] = dis[curNode] + 1;
} else if(clr[nbr] != nextClr) {
return 0;
}
}
q.pop();
}
return true;
}
int getMaximumSplits(int node) {
for(auto &newNodes : newVisitedNodes) {
dis[newNodes] = -1;
}
queue<int> q;
q.push(node);
dis[node] = 0;
int farthestNodeDistance = -1;
while(q.size()) {
int curNode = q.front();
farthestNodeDistance = max(farthestNodeDistance, dis[curNode]);
for(auto nbr: graph[curNode]) {
if(dis[nbr] == -1) {
q.push(nbr);
dis[nbr] = dis[curNode] + 1;
}
}
q.pop();
}
return farthestNodeDistance + 1;
}
int magnificentSets(int n, vector<vector<int>>& edges) {
int ans = 0;
clr = vector<int>(n+1,-1);
dis = vector<int>(n+1,-1);
graph = vector<vector<int>>(n+1);
for(auto &edge: edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
for(int i = 1 ; i <= n ;i++) {
if(dis[i] == -1) {
if(hasBipartiteSplit(i)) {
int mx = -1;
for(auto & newNode : newVisitedNodes) {
mx = max(mx, getMaximumSplits(newNode));
}
ans += mx;
} else {
return -1;
}
}
}
return ans;
}
};
