Niloy007

SSSP

Jun 18th, 2020
110
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector<int> gr[1000];
  4. bool vis[1000];
  5. int dis[1000];
  6.  
  7. void dfs(int u, int d) {
  8.     vis[u] = true;
  9.     dis[u] = d;
  10.     for (int v : gr[u]) {
  11.         if (!vis[v]) {
  12.             dfs(v, d + 1);
  13.         }
  14.     }
  15. }
  16.  
  17. int main() {
  18.     int n, m, a, b, t;
  19.     cin >> n >> m;
  20.     for (int i = 0; i < m; i++) {
  21.         cin >> a >> b;
  22.         gr[a].push_back(b);
  23.         gr[b].push_back(a);
  24.     }
  25.     dfs(2, 0);
  26.  
  27.     int max = 0;
  28.     for (int i = 0; i < n; i++) {
  29.         if(max < dis[i]) {
  30.             max = dis[i];
  31.         }
  32.     }
  33.     cout << max << endl;
  34.     for (int i = 1; i <= n; i++) {
  35.         cout << dis[i] << " ";
  36.     }
  37.     cout << "\n";
  38.     return 0;
  39. }
RAW Paste Data