How to solve this graph problem in O(N^2) ?

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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;
    }
};

//(c) A+ Computer Science //www.apluscompsci.com //Name - Srinivas Potnuru //stores a thing and a count of how many times the thing is there package LinkedList; public class ThingCount implements Comparable { private int count; private Object thing; public ThingCount() { this(null, 0); } public ThingCount(Object thang, int cnt) { thing = thang; count = cnt; } public int getCount() { return count; } public void setCount(int cnt) { count = cnt; } public void setThing(Object obj) { thing = obj; } public Object getThing() { return thing; } public boolean equals(Object obj) { ThingCount other = (ThingCount)obj; return other.getThing().equals(getThing()); } public int compareTo(Object obj) { ThingCount other = (ThingCount)obj; if (!getThing().getClass().equals(other.getThing().getClass())) { throw new RuntimeException("both objects are not of the same type"); } return getThing().toString().compareTo(other.getThing().toString()); } public String toString() { return ""+ getThing() + " - " + getCount(); } }

Comments (12)

Write comment?

The-Winner

12 days ago, # |

+15

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).

→ Reply

drexdelta

12 days ago, # ^ |

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.

← Rev. 3 →

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.)

Leonardo_Paes

-13

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.net/blog/entry/60440#:~:text=1)%20Choose%20a%20random%20node,%2Cv)%20is%20the%20diameter.

← Rev. 2 →

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.

-10

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.

← Rev. 5 →

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.

lotusblume

+17

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.

Code

#include <iostream>
#include <vector>

int main() {
	int n, m;
	std::cin >> n >> m;

	std::vector<std::vector<bool>> adj(n, std::vector<bool>(n, false));

	for (int i = 0; i < m; ++i) {
		// 0 <= u, v < n
		int u, v;
		std::cin >> u >> v;
		adj[u][v] = adj[v][u] = true;
	}

	// dp[v][mask] = true, if there exists a path that ends in v and visits
	//               all vertices whos bits in mask are set to 1
	//
	// example: if dp[2][13] = true (in binary dp[2][1101]) would mean that
	// there exists a path that visits vertices 0,2,3 and ends in vertex 2
	std::vector<std::vector<bool>> dp(n, std::vector<bool>(1 << n, false));

	// trivial cases
	for (int v = 0; v < n; ++v) {
		dp[v][1 << v] = true;
	}

	for (int mask = 0; mask < (1 << n); ++mask) {
		for (int v = 0; v < n; ++v) {
			if (!dp[v][mask]) continue;
			for (int next = 0; next < n; ++next) {
				// edge (v, next) exists and next has not already been visited?
				if (adj[v][next] && !(mask & (1 << next))) {
					dp[next][mask | (1 << next)] = true;
				}
			}
		}
	}

	// length of longest path
	int ans = 0;

	for (int v = 0; v < n; ++v) {
		for (int mask = 0; mask < (1 << n); ++mask) {
			if (dp[v][mask]) {
				ans = std::max(ans, __builtin_popcount(mask));
			}
		}
	}

	std::cout << ans << '\n';

	return 0;
}

orz69

-32

asdasdqwer

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.

drexdelta's blog