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;
}
};
Prety sure that the result is the diameter of the graph. As far as I know you cannot do that faster than $$$O(N*M)$$$, but there exist approximate algorithms that run in $$$O(N+M)$$$ and have an approximation factor of $$$2$$$. (I don't know if there are other algorithms that have been discovered/invented for graph diameters that are better).
I am not that expert in the graph theory. How to find diameter in such a cyclic graph ?
case
What you drew is not the diameter. In a general graph the diameter is defined as the maximum minimum distance between two nodes. That is: Take all pairs of nodes and compute the distance between them. The maximum of these values is the diameter.
understood. Thanks. Helpful. I saw one solution, which did floyd-warshal to find distances of each pair, and then took maximum of it. I understood it now, earlier I couldn't .
Now, Coming to the above diagram, (just in case if you have time)
how to find length of longest path in undirected graph, where every node is visited only once the path. ( I can't think anything but brute-dfs from each node.)
It's a classic problem that can be solved in O(n + m). One of the ways you can solve it is by DFS from an arbitrary node u and finding any farthest node from it. Let such node be v. Now, the claim is that the farthest node from v is the diameter of the graph. So, calling DFS twice finds such longest simple path.
This might help: https://codeforces.me/blog/entry/60440#:~:text=1)%20Choose%20a%20random%20node,%2Cv)%20is%20the%20diameter.
Try running your algorithm on the graph I have drawn above. Take left most node as initial random node, and see, if it it works.
The algo you shared, it works when you don't have cycles.
Oh sorry about it. You solve the cyclic version in O(N^2 log n) by running dijkstra starting at every node. I'm not sure if you can do better with edge weights <= 10^4.
How will that help ?
If you can provide some POC, i will be grateful.
Guys I thought he meant longest minimum path (aka diameter). I was suggesting a way to find the diameter of a cyclic graph by running a dijkstra from every node. But it's ok.
Finding a longest path is NP-Hard: https://en.wikipedia.org/wiki/Longest_path_problem
Probably the best algorithm to find a longest path is a dp with running time O(2^n * n^2).
Where for every vertex v (n choices) and subset of vertices S (2^n choices) you set dp[v][S] = true, if there exists a path that ends in v and visits exactly the vertices in S.
A convenient way to implement this, is using bitmasks.
If you have a cycle with an odd length, then such a grouping is not possible. You can check that with a simple bipartite-checking algorithm, which runs in $$$O(n+m)$$$. Now that we know that the graph is bipartite, the answer is the diameter of the graph. A simple approach would be to start a BFS from each node, which would run in $$$O(n*m)$$$. Maybe we can use the bipartite property to calculate the diameter of the graph more efficiently, however I don't know how that would be done.