Facebook
From amsen, 9 Months ago, written in C++.
Embed
Download Paste or View Raw
Hits: 57
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<ii, int> iii;
  8.  
  9. const int N = 3e5+100;
  10.  
  11. struct graph
  12. {
  13.         int n;
  14.         vector<int> adj[N];
  15.  
  16.         graph(int n) : n(n){
  17.         fill(adj, adj+n, vector<int>());
  18.     }
  19.  
  20.         void add_edge(int u, int v)
  21.         {
  22.                 adj[u].push_back(v);
  23.                 adj[v].push_back(u);
  24.         }
  25.        
  26.         vector<int>& operator[](int u) { return adj[u]; }
  27. };
  28.  
  29. vector<vector<int>> biconnected_components(graph &adj)
  30. {
  31.         int n = adj.n;
  32.  
  33.         vector<int> num(n), low(n), art(n), stk;
  34.         vector<vector<int>> comps;
  35.  
  36.         function<void(int, int, int&)> dfs = [&](int u, int p, int &t)
  37.         {
  38.                 num[u] = low[u] = ++t;
  39.                 stk.push_back(u);
  40.  
  41.                 for (int v : adj[u]) if (v != p)
  42.                 {
  43.                         if (!num[v])
  44.                         {
  45.                                 dfs(v, u, t);
  46.                                 low[u] = min(low[u], low[v]);
  47.  
  48.                                 if (low[v] >= num[u])
  49.                                 {
  50.                                         art[u] = (num[u] > 1 || num[v] > 2);
  51.  
  52.                                         comps.push_back({u});
  53.                                         while (comps.back().back() != v)
  54.                                                 comps.back().push_back(stk.back()), stk.pop_back();
  55.                                 }
  56.                         }
  57.                         else low[u] = min(low[u], num[v]);
  58.                 }
  59.         };
  60.  
  61.         for (int u = 0, t; u < n; ++u)
  62.                 if (!num[u]) dfs(u, -1, t = 0);
  63.        
  64.     return comps;
  65. }
  66.  
  67. iii e[N];
  68. int cnt[N];
  69. bool mark[2][N];
  70. set<int> c[N];
  71.  
  72. int get_cmn(set<int> &f, set<int> &s){
  73.     if(f.size() > s.size())
  74.         f.swap(s);
  75.     for(auto v : f)
  76.         if(s.count(v))
  77.             return v;
  78.     return -1;
  79. }
  80.  
  81. signed main(){
  82.         ios_base::sync_with_stdio(false);cin.tie(NULL);
  83.     int n, m;cin >> n >> m;
  84.     graph g = graph(n);
  85.     for(int i=0 ; i<m ; i++){
  86.         int v, u, w;cin >> v >> u >> w;v --;u --;
  87.         e[i] = iii(ii(v, u), w);
  88.         g.add_edge(v, u);
  89.     }
  90.  
  91.     auto cmps = biconnected_components(g);
  92.     int sz=0;
  93.     for(auto cmp : cmps){
  94.         for(auto i : cmp){
  95.             c[i].insert(sz);
  96.             cnt[sz] ++;
  97.         }
  98.         sz ++;
  99.     }
  100.     int all = 0;
  101.     for(int i=0 ; i<m ; i++){
  102.         int v = e[i].first.first, u = e[i].first.second, w = e[i].second;
  103.         int cmn = get_cmn(c[v], c[u]);
  104.         if(cmn > -1){
  105.             mark[w][ cmn ] = true;
  106.         }else
  107.             all ^= w;
  108.     }
  109.     for(int i=0 ; i<sz ; i++){
  110.         if(mark[1][i])
  111.             all ^= (cnt[i] - 1);
  112.         if(mark[0][i] && mark[1][i]){
  113.             cout << "YES\n";
  114.             return 0;
  115.         }
  116.     }
  117.     cout << (all%2 == 1 ? "YES" : "NO") << "\n";
  118. }
  119.