Graph Girth

 Problem Link

Tags: BFS
Time Complexity: O(N²)

In this problem, an undirected unweighted graph is given, and we are asked to find the length of the shortest cycle, if any.

Since the graph edges are unweighted, BFS can be used to find the shortest path from the starting node to all other nodes. But, we do not know which nodes are part of the cycle, so where do we start the BFS?

Since N ≤ 2500, we can run BFS from every node and keep track of the shortest cycle length. For each BFS-run, we keep track of the number of edges traversed (aka distance) to reach the current node from the starting node. If we visit a node that has already been visited, then it means the shortest cycle that includes the starting node has been found. Let's call this node y and call the node which visited node y for a second time, x. To find the length of this cycle, simply add the distance travelled by the x, to the distance travelled by node y and one to include the edge between x and y.

The answer is the minimum of all the cycle lengths.

Code

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2501;

bool visited[MAX_N];

vector <vector <int>> adj(MAX_N);

int dis[MAX_N];

int came_from[MAX_N];

vector <int> ans;

int main()

{

    int n, m;

    cin >> n >> m;

    for (int i = 0; i < m; i++){

        int a, b;

        cin >> a >> b;

        adj[a].push_back(b);

        adj[b].push_back(a);

    }

    int min_len = INT_MAX;

    for (int i = 1; i <= n; i++){

        queue <pair <int, int>> q;

        q.push({0, i});

        while (!q.empty()){

            int a = q.front().second, p = q.front().first;

            q.pop();

            for (auto j : adj[a]){

                if (j == p)

                    continue;

                if (visited[j]){ //found cycle

                    min_len = min(min_len, dis[a] + dis[j] + 1);

                    continue;

                }

                dis[j] = dis[a] + 1;

                visited[j] = true;

                q.push({a, j});

                came_from[j] = a;

            }

        }

        memset(visited, 0, sizeof(visited));

        memset(dis, 0, sizeof(dis));

        memset(came_from, 0, sizeof(came_from));

    }

    if (min_len == INT_MAX)

        cout << -1 << '\n';

    else

        cout << min_len << '\n';

}