fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define nmax int(1e5+7)
  3. using namespace std;
  4. int n, m, cnt, par[nmax*2];
  5. pair<int,int> a[nmax];
  6. vector <int> tmp;
  7. int find_set(int u){
  8.     if (u == par[u]) return u;
  9.     return par[u] = find_set(par[u]);
  10. }
  11. bool union_set(int L, int R){
  12.     int dest = find_set(R+1);
  13.     bool ok = true;
  14.     while (L <= R){
  15.         int x = find_set(L);
  16.         if (x != L) ok = false;
  17.         par[x] = dest;
  18.         L = x + 1;
  19.     }
  20.     return ok;
  21. }
  22. int main(){
  23.     cin >> m >> n;
  24.     for (int i=1; i<=n; i++){
  25.         cin >> a[i].first >> a[i].second;
  26.         tmp.push_back(a[i].first); tmp.push_back(a[i].second);
  27.     }
  28.     sort(tmp.begin(), tmp.end());
  29.     for (int i=1; i<=n; i++){
  30.         a[i].first = lower_bound(tmp.begin(), tmp.end(), a[i].first) - tmp.begin();
  31.         a[i].second = lower_bound(tmp.begin(), tmp.end(), a[i].second) - tmp.begin();
  32.     }
  33.     for (int i=1; i<=2*n+1; i++)par[i] = i;
  34.     for (int i=n; i>=1; i--)cnt += union_set(a[i].first, a[i].second);
  35.     cout << cnt;
  36. }
  37. /*
  38.     Solve by: Truong Tuan Kiet - Informatics K36. Solve in 11h00 - 7/4/2025
  39. */
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/w6CVFE
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!