fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. vector<vector<int>> wektor;
  7. vector<int> odwiedzone;
  8. vector<int> komponent; // Przechowuje numer komponentu spójności dla każdego wierzchołka
  9.  
  10. void BFS(int V, int componentId) {
  11.     queue<int> q;
  12.     q.push(V);
  13.     odwiedzone[V] = 1;
  14.     komponent[V] = componentId; // Przypisanie wierzchołka do komponentu
  15.  
  16.     while (!q.empty()) {
  17.         int p = q.front();
  18.         q.pop();
  19.  
  20.         for (int j : wektor[p]) {
  21.             if (odwiedzone[j] == 0) {
  22.                 odwiedzone[j] = 1;
  23.                 komponent[j] = componentId; // Przypisanie wierzchołka do komponentu
  24.                 q.push(j);
  25.             }
  26.         }
  27.     }
  28. }
  29.  
  30. int main() {
  31.     int a {0}, b {0};
  32.     int ile_v {0};
  33.     int ile_e {0};
  34.  
  35.     // Wczytaj liczbę plemion i dróg
  36.     cin >> ile_v >> ile_e;
  37.  
  38.     wektor.resize(ile_v + 1);
  39.     odwiedzone.resize(ile_v + 1, 0);
  40.     komponent.resize(ile_v + 1, 0);
  41.  
  42.     // Wczytaj drogi
  43.     for (int i = 0; i < ile_e; i++) {
  44.         cin >> a >> b;
  45.         wektor[a].push_back(b);
  46.         wektor[b].push_back(a);
  47.     }
  48.  
  49.     // Znajdź komponenty spójności
  50.     int componentId = 0;
  51.     for (int i = 1; i <= ile_v; i++) {
  52.         if (odwiedzone[i] == 0) {
  53.             componentId++;
  54.             BFS(i, componentId);
  55.         }
  56.     }
  57.  
  58.     // Wczytaj liczbę zapytań
  59.     int ile_q {0};
  60.     cin >> ile_q;
  61.  
  62.     // Odpowiedz na zapytania
  63.     for (int i = 0; i < ile_q; i++) {
  64.         int p, k;
  65.         cin >> p >> k;
  66.         if (komponent[p] == komponent[k]) {
  67.             cout << "TAK\n";
  68.         } else {
  69.             cout << "NIE\n";
  70.         }
  71.     }
  72.  
  73.     return 0;
  74. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
8 6
1 2
5 7
3 2
5 8 
1 3
2 4
4  
1 4
6 7
7 5
3 8
stdout
copy 
TAK
NIE
TAK
NIE
https://ideone.com/dNuYsV
language:
C++14 (gcc 8.3)
created:
1 day 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!