[NEW] Add solution for Message Route

[vingoel26]

🎯 Problem Information

• Problem Name: Message Route
• CSES Link: https://cses.fi/problemset/task/1667
• Category: Graph
• Estimated Difficulty: Medium

📋 Problem Description

Syrjälä's network has n computers and m connections. Your task is to find out if Uolevi can send a message to Maija, and if it is possible, what is the minimum number of computers on such a route.

💡 Proposed Approach

Describe the algorithm/approach you plan to use:

• The code implements Breadth-First Search (BFS) to find the shortest path between two nodes (1 → n) in an unweighted, undirected graph.

• BFS ensures the shortest path in terms of edge count, since it explores all nodes level by level.

• It maintains:

  • d[i] → distance of node i from source (1)
  • par[i] → parent of node i in the shortest path tree

• Once BFS completes, the path is reconstructed by backtracking using the parent array.

• Time Complexity: O(N + M)

• Space Complexity: O(N + M)

---

📝 Implementation Notes

Any special considerations or optimizations needed:

• Requires fast I/O (ios::sync_with_stdio(0) and cin.tie(0))
• Needs modular arithmetic
• Handles large input constraints (N ≤ 1e5, M ≤ 2e5)
• Edge cases to consider:
  • Graph is disconnected (output “IMPOSSIBLE”)
  • Source and destination are the same
  • Multiple shortest paths (any valid one can be printed)

---

🏷️ Labels

Please add appropriate labels:

• hacktoberfest
• good first issue
• help wanted

---

👤 Assignee

• I would like to work on this issue
• I'm available for guidance/review

---

📎 Additional Context

This problem demonstrates BFS traversal to find the shortest path in an unweighted graph, typically used in competitive programming and graph theory practice.
If there’s no path between node 1 and n, the code prints "IMPOSSIBLE".

---

🧠 Code Implementation

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9;
const int N = 1e5 + 9;
vector<int> g[N];

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  queue<int> q;
  vector<int> d(n + 1, inf), par(n + 1, -1);
  q.push(1);
  d[1] = 0;

  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto v : g[u]) {
      if (d[u] + 1 < d[v]) {
        d[v] = d[u] + 1;
        par[v] = u;
        q.push(v);
      }
    }
  }

  if (d[n] == inf) {
    cout << "IMPOSSIBLE\n";
    return 0;
  }

  cout << d[n] + 1 << '\n';
  int cur = n;
  vector<int> path;
  while (cur != -1) {
    path.push_back(cur);
    cur = par[cur];
  }
  reverse(path.begin(), path.end());
  for (auto u : path) {
    cout << u << ' ';
  }
  cout << '\n';
  return 0;
}

[vingoel26]

@ks-iitjmu Please assign this to me

[ks-iitjmu]

@vingoel26 Assigned