usth/MATH2.3/2/connected.cc


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

int
main ()
{
  size_t n, a, b;
  unordered_map<size_t, unordered_set<size_t>> edges;

  cin >> n;
  for (size_t i = 0; i < n; ++i)
    {
      cin >> a >> b;
      edges[a].insert (b);
      edges[b].insert (a);
    }

  unordered_set<size_t> s;
  size_t count = 0;
  for (auto const& [v, p] : edges)
    {
      if (s.count (v))
        continue;
      count++;
      vector<size_t> fifo {v};
      while (!fifo.empty ())
        {
          size_t u = fifo.back ();
          fifo.pop_back ();
          if (s.count (u))
            continue;
          s.insert (u);
          for (auto const& w : edges[u])
            if (!s.count (w))
              fifo.push_back (w);
        }
    }

  cout << count << endl;
}