usth/MATH2.3/2/bipartite.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
45
46
47
48
49
50
51
52
53
54
55

#include <iostream>
#include <queue>
#include <unordered_map>
#include <set>

using namespace std;

int
main ()
{
  unordered_map<size_t, unordered_map<size_t, size_t>> adj;
  size_t n, u, v;
  cin >> n;
  while (n--)
    {
      cin >> u >> v;
      adj[u][v]++;
      adj[v][u]++;
    }

  queue<size_t> q;
  set<size_t> one, another;
  q.push (u);
  one.insert (u);

  while (!q.empty ())
    {
      u = q.front ();
      q.pop ();
      if (adj[u][u])
        {
          cout << "no" << endl;
          return 0;
        }
      for (auto const& [v, b] : adj[u])
        {
          if (!b)
            continue;
          if (one.count (v) && one.count (u)
              || another.count (v) && another.count (u))
            {
              cout << "no" << endl;
              return 0;
            }
          if (one.count (v) || another.count (v))
            continue;
          q.push (v);
          if (one.count (u))
            another.insert (v);
          else
            one.insert (v);
        }
    }
  cout << "yes" << endl;
}