Maximal ring and longest chain of Graphs

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, 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) {
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].push_back(edge);
graph[edge].push_back(edge);
}
memset(vis, 0, sizeof(vis));
dfs(0, 0, 0);  // end is rightmost node
memset(vis, 0, sizeof(vis));
dfs(end, 0, 1);  // end is leftmost node

// cout << end << " " << end << endl;

vector<int>path = {end};
memset(vis, 0, sizeof(vis));
path_dfs(end, 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.