Hydron

Обход графа

Dec 7th, 2021 (edited)
197
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 KB | None | 0 0
  1. /// https://informatics.msk.ru/mod/statements/view3.php?chapterid=164#1
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. int main(){
  7.     int n, s;
  8.     cin >> n >> s;
  9.     int graph[n+1][n+1];
  10.     vector < int > g[n+1];
  11.     for (int i=1; i<=n; i++){
  12.         for (int j=1; j<=n; j++){
  13.             cin >> graph[i][j];
  14.             if (graph[i][j] == 1){
  15.                 g[i].push_back(j);
  16.                 //g[j].push_back(i);
  17.             }
  18.         }
  19.     }
  20.     int used[n+1]; // used[i] = 1, якщо <i> Була відвідана
  21.     for (int i=0; i<=n; i++) used[i] = 0;
  22.     vector < int > q;
  23.     q.push_back(s);
  24.     used[s] = 1;
  25.     int point = 0;
  26.     while(point < q.size()){
  27.         int v = q[point];
  28.         for (int i=0; i<g[v].size(); i++){
  29.             int to = g[v][i];
  30.             if (used[to] == 0){
  31.                 used[to] = 1;
  32.                 q.push_back(to);
  33.             }
  34.         }
  35.         point ++;
  36.     }
  37.     cout << q.size();
  38.     return 0;
  39. }
Add Comment
Please, Sign In to add comment