This is a very basic problem in graphs. Many graph problems can be transformed into finding the largest ring or longest chain in graphs.
For example, Leetcode 5970 The maximum number of employees participating in the meeting is equivalent to finding the longest ring of a directed graph and the ring with length 2 plus its outer chain.
Directed graph
Maximum ring
There are many ways:
- One is to remove the outer chain by topological sorting, and then dfs each ring
- The other is to start from a certain point and record the point of the path. If you encounter a point that has been visited, it indicates that the entrance of the ring has been found. Minus the distance from the starting point to the entrance is the length of the ring.
- There is also a union search set. For X - > y, if x and Y belong to the same set, it means that a ring is formed.
The way to find the minimum ring is similar.
Suppose favor [i] = V means that there is an edge from I to I, and the second method is adopted here
int DirectMaxCycle(vector<int>& favorite) {
int n = favorite.size();
vector<bool> vis(n, false);
int max_cycle = 0;
for(int i = 0;i < n;i++) {
if(vis[i]) continue;
int cur = i;
vector<int> cycle;
while(!vis[cur]) {
vis[cur] = true;
cycle.push_back(cur);
cur = favorite[cur];
}
for(int j = 0;j < cycle.size();j++) {
if(cycle[j] == cur) {
int len = cycle.size() - j;
if(len > max_cycle) max_cycle = len;
break;
}
}
}
return max_cycle;
}
Directed acyclic graph: longest chain
Here is a very important question. What if there is a ring?
In the case of rings, it is meaningless to find the longest chain. Either ensure that there is no ring, or find the length of the chain connected to the ring.
For example, to find the length of the chain connected to the ring, you need to start with the node with a penetration of 0 and calculate it recursively, so the topological order is adopted.
int TopologicalSort(vector<int>& favorite) {
int n = favorite.size();
vector<bool> vis(n, false);
vector<int>in(n, 0);
vector<int>dp(n, 1);
queue<int> q;
for(int i = 0;i < n;i++) in[favorite[i]]++;
for(int i = 0;i < n;i++) {
if(in[i] == 0) q.push(i);
}
while(!q.empty()) {
int cur = q.front();
q.pop();
// cout << cur << " ";
dp[favorite[cur]] = max(dp[favorite[cur]], dp[cur] + 1);
if(--in[favorite[cur]] == 0) q.push(favorite[cur]);
}
// dp[i] represents the length of the longest chain reaching I
int two_point_sum = 0; // Relevant parts of the topic
for(int i = 0;i < n;i++) {
if(i == favorite[favorite[i]]) two_point_sum += dp[i];
}
return two_point_sum;
}
Undirected graph
Maximum ring
Similar to directed graph, omitted
Undirected acyclic graph: longest chain
Because it is an acyclic graph, finding the longest chain is to find the diameter of the tree
- It can also be the same as a directed graph, topological order + dp
- There is another interesting method, twice dfs. It can be proved that the farthest point that dfs can reach from any point must be an end point of "diameter", and then starting from this end point, dfs gets another end point.
For example, the minimum decimal height of leetcode 310 is equivalent to finding the diameter of the tree
The first time dfs finds an endpoint, then starts from this endpoint, dfs finds another endpoint, and finally writes a dfs to get the path
class Solution {
public:
static const int maxn = 20000+10;
vector<int>graph[maxn];
bool vis[maxn];
int end[2], max_dis=-1;
void dfs(int s, int dis, int flag) {
vis[s] = true;
if(dis >= max_dis) {max_dis = dis; end[flag] = s;}
for(int i = 0; i < graph[s].size(); i++) {
int t = graph[s][i];
if(!vis[t]) {
dfs(t, dis+1, flag);
}
}
}
vector<int>ans;
void path_dfs(int s, int dis, vector<int>& path) {
if(s == end[1]) {
int n = path.size();
// cout << "path: ";
// for(int i = 0; i < n; i++) {
// cout << path[i] << " ";
// }
// cout << endl;
if(n%2 == 0) ans = {path[n/2-1], path[n/2]};
else ans = {path[n/2]};
return;
}
vis[s] = true;
for(int i = 0; i < graph[s].size(); i++) {
int t = graph[s][i];
if(!vis[t]) {
path.push_back(t);
path_dfs(t, dis+1, path);
path.pop_back();
}
}
}
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
for(auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
memset(vis, 0, sizeof(vis));
dfs(0, 0, 0); // end[0] is rightmost node
memset(vis, 0, sizeof(vis));
dfs(end[0], 0, 1); // end[1] is leftmost node
// cout << end[0] << " " << end[1] << endl;
vector<int>path = {end[0]};
memset(vis, 0, sizeof(vis));
path_dfs(end[0], 0, path);
return ans;
}
};
It can also be written in double BFS, and compared with the previous DFS, BFS can get the path when seeking the farthest point
int bfs(int s){ // Returns the farthest point from s
memset(vis, 0, sizeof(vis));
queue<int>q;
q.push(s);
vis[s] = true;
int u;
while(!q.empty()){
u = q.front();
q.pop();
for(int i = 0; i < graph[u].size(); i++){
int v = graph[u][i];
if(!vis[v]){
vis[v] = true;
q.push(v);
}
}
}
return u;
}
int pre[maxn];
vector<int> path_bfs(int s) { // Returns the path from s to end
memset(vis, 0, sizeof(vis));
memset(pre, -1, sizeof(pre));
queue<int>q;
q.push(s);
vis[s] = true;
int u;
while(!q.empty()){
u = q.front();
q.pop();
for(int i = 0; i < graph[u].size(); i++){
int v = graph[u][i];
if(!vis[v]){
vis[v] = true;
q.push(v);
pre[v] = u;
}
}
}
vector<int>path;
while(u != -1){
path.push_back(u);
u = pre[u];
}
return path;
}
be careful
In a ring graph, the double dfs/bfs method is wrong, and it is easy to find a counterexample:
Picture from The time complexity of finding the diameter of a graph
The result obtained by the above method may be 4, but it is actually 5.
Reference link
- Blue Bridge Cup -- children's worship circle (seeking the largest ring of directed graph)
- 019 Niuke multi School Game 4 A meeting - tree diameter
- Rogu-P2661 information transmission -- the smallest ring in a directed graph
- Leetcode directed graph longest Ring + topological sorting
- Leetcode finds the diameter of the tree