Online feud

#include <bits/stdc++.h>
using namespace std;
// clang-format off
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
template <typename T> istream &operator>>(istream &is, vector<T> &v) { T value; is >> value; v.push_back(value); return is; }
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#ifdef DO_DBG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
template <typename T> using v = vector<T>;
template <typename T> using us = unordered_set<T>;
template <typename K, typename V> using um = unordered_map<K, V>;
template <typename K, typename V> using p = pair<K, V>;
template <typename T> using pq = priority_queue<T>;
template <typename T> using nl = numeric_limits<T>;
constexpr int MOD = 1e9 + 7;
const int INF = 1e9;
const ld EPS = 1e-9;
#define loopi(n) for (int i = 0; i < n; i++)
#define loopj(n) for (int j = 0; j < n; j++)
#define loopk(n) for (int k = 0; k < n; k++)
#define loopz(n) for (int z = 0; z < n; z++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sq(x) ((x) * (x))
#define basic ll n; cin >> n; v<ull> a; loopi(n) cin >> a;
// clang-format on

class UF {
public:
  v<int> uf;
  v<int> size;

  UF(int n) {
    uf.resize(n);
    size.resize(n);
    loopi(n) uf[i] = i;
    loopi(n) size[i] = 1;
  }

  int find(int x) {
    while (x != uf[x])
      x = uf[x];
    return x;
  }

  void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (size[a] < size[b])
      swap(a, b);
    size[a] += size[b];
    uf[b] = a;
  }
};

// we can first process the likes,
// doing a union find to split people into multiple sets based on their likes
//
// after that we can simplify the problem to having n people with *only*
// dislikes taken into account. we can just consider the dislikes as edges and
// find out if the graph is bipartite
UF uf(0);
v<set<int>> adj;
v<char> color;

bool dfs(int i) {
  for (auto a : adj[i]) {
    if (color[a] != 0) {
      if (color[a] == color[i])
        return false;
    } else {
      color[a] = color[i] == 1 ? 2 : 1;
      if (!dfs(a))
        return false;
    }
  }
  return true;
}

int main() {
  fastio;
  int n, m;
  cin >> n >> m;
  v<pair<int, int>> dislikes;
  uf = UF(n);
  adj = v<set<int>>(n);
  color = v<char>(n);

  loopi(m) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    if (c == 1) {
      uf.unite(a, b);
    } else {
      dislikes.push_back({a, b});
    }
  }
  for (auto d : dislikes) {
    int a = d.first;
    int b = d.second;
    adj[uf.find(a)].insert(uf.find(b));
    adj[uf.find(b)].insert(uf.find(a));
  }

  dbg(adj);
  // do bipartite check
  bool bip = true;
  loopi(n) {
    if (color[i] == 0) {
      color[i] = 1;
      if (!dfs(i)) {
        bip = false;
        break;
      }
    }
  }
  if (bip) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED

Test 60

Verdict: ACCEPTED

Test 61

Verdict: ACCEPTED

Test 62

Verdict: TIME LIMIT EXCEEDED

Test 63

Verdict: ACCEPTED

Test 64

Verdict: ACCEPTED

Test 65

Verdict: TIME LIMIT EXCEEDED

Test 66

Verdict: TIME LIMIT EXCEEDED

Test 67

Verdict: ACCEPTED

Test 68

Verdict: TIME LIMIT EXCEEDED

Test 69

Verdict: ACCEPTED

Test 70

Verdict: ACCEPTED

Test 71

Verdict: ACCEPTED