fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. using namespace std;
  6. const int X = 500000;
  7. vector<int> znajomosc[X];
  8. bool odwiedzony[X];
  9. int odleglosc[X];
  10. void uncharted_map(int start) {
  11.     queue<int> q;
  12.     q.push(start);
  13.     odwiedzony[start] = true;
  14.     odleglosc[start] = 0;
  15.     while (!q.empty()) {
  16.         int u = q.front();
  17.         q.pop();
  18.         for (int v : znajomosc[u]) {
  19.             if (!odwiedzony[v]) {
  20.                 odwiedzony[v] = true;
  21.                 odleglosc[v] = odleglosc[u] + 1;
  22.                 q.push(v);
  23.             }
  24.         }
  25.     }
  26. }
  27. int main() {
  28.     ios::sync_with_stdio(false);
  29.     cin.tie(0);
  30.     int Z;
  31.     cin >> Z;
  32.     while (Z--) {
  33.         int n, m;
  34.         cin >> n >> m;
  35.         for (int i = 1; i <= n; ++i) {
  36.             znajomosc[i].clear();
  37.             odwiedzony[i] = false;
  38.             odleglosc[i] = -1;
  39.         }
  40.         for (int i = 0; i < m; ++i) {
  41.             int a, b;
  42.             cin >> a >> b;
  43.             znajomosc[a].push_back(b);
  44.             znajomosc[b].push_back(a);
  45.         }
  46.         int moj_numer;
  47.         cin >> moj_numer;
  48.         uncharted_map(moj_numer);
  49.         cout << "Znajomi numeru " << moj_numer << ":\n";
  50.         vector<pair<int, int>> wyniki;
  51.         for (int i = 1; i <= n; ++i) {
  52.             if (i != moj_numer && odleglosc[i] != -1) {
  53.                 wyniki.emplace_back(i, odleglosc[i]);
  54.             }
  55.         }
  56.         sort(wyniki.begin(), wyniki.end());
  57.         for (auto [kto, odl] : wyniki) {
  58.             cout << kto << ": " << odl << "\n";
  59.         }
  60.         int grupy = 0;
  61.         for (int i = 1; i <= n; ++i) {
  62.             if (!odwiedzony[i]) {
  63.                 uncharted_map(i);
  64.                 grupy++;
  65.             }
  66.         }
  67.         cout << "Grup znajomych jest " << (grupy + 1) << ".";
  68.     }
  69.     return 0;
  70. }
Success #stdin #stdout 0.01s 16984KB
comments (?)
stdin
copy 
1
8 7
1 2
1 3
2 4
3 4
4 8
6 7
5 8
5
stdout
copy 
Znajomi numeru 5:
1: 4
2: 3
3: 3
4: 2
8: 1
Grup znajomych jest 2.
https://ideone.com/wVn404
language:
C++ (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!