Advertisement
oleg_drawer

dfs unorient graf

Apr 10th, 2020
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector< vector <int> > g(0);
  5.  
  6.  
  7. vector<bool> used(0);
  8.  
  9. void dfs(int v){
  10.     used[v] = true;
  11.     for(auto u : g[v]){
  12.         if(!used[u])
  13.             dfs(u);
  14.     }
  15. }
  16.  
  17. int main() {
  18.  
  19.     int n,m;
  20.     cin >> n;   // нам говорят, что в нашем графе n вершин
  21.     g.resize(n,vector<int>(0));
  22.     used.resize(n,false);
  23.     cin >> m;   //нам говорят, что будет введено m ребер
  24.     for(int i = 0; i < m; i++){
  25.         int v,u;
  26.         cin >> v >> u;  // нам вводят ребро (v -> u)
  27.         v--;
  28.         u--; // мы это делаем, т к в нашем графе нумерация вершин [0 .. n-1], а в задаче -- [1 .. n]
  29.         g[v].push_back(u);  // мы добавляем ребро (v -> u) в граф
  30.         g[u].push_back(v);  // мы добавляем ребро (u -> v) в граф
  31.     }
  32.    
  33.     int cnt = 0;
  34.     for(int i = 0; i < n; i++){
  35.         if(!used[i]){
  36.             cnt++;
  37.             dfs(i);
  38.         }
  39.     }
  40.  
  41.     return 0;
  42. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement