fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. void dfs2(int node, vector<bool> &visited, vector<vector<int> > &adjList, int &minval, int &maxval)
  4. {
  5.     visited[node] = true;
  6.     minval = min(minval, node);
  7.     maxval = max(maxval, node);
  8.     for(auto &neighbour : adjList[node])
  9.         if(!visited[neighbour])
  10.             dfs2(neighbour,visited,adjList,minval,maxval);
  11.     return;
  12. }
  13. void dfs(vector<vector<int> > &adjList, int &V, vector<pair<int,int> > &minmax)
  14. {
  15.     vector<bool> visited(V,false);
  16.     for(int node = 0; node < V; node++)
  17.         if(!visited[node])
  18.         {
  19.         	int minval = 200000;
  20.         	int maxval = -1;
  21.             dfs2(node,visited,adjList,minval,maxval);
  22.             if(minval!=maxval) minmax.push_back({minval,maxval});
  23.         }
  24.     return;
  25. }
  26. class SetUnion
  27. {
  28. public:
  29.     struct Node
  30.     {
  31.         int rank;
  32.         int parent;
  33.     };
  34.     unordered_map <int,Node> st;
  35.     void makeSet(vector<int> &v)
  36.     {
  37.         for(int &i : v) st[i] = {1,i};
  38.     }
  39.     int find_root(int data)
  40.     {
  41.         if(st[data].parent == data) return data;
  42.         st[data].parent = find_root(st[data].parent);
  43.         return st[data].parent;
  44.     }
  45.     bool do_union(int data1, int data2)
  46.     {
  47.         int x = find_root(data1);
  48.         int y = find_root(data2);
  49.         if(x == y) return false;
  50.         if(st[x].rank > st[y].rank) st[y].parent = x;
  51.         else if(st[y].rank > st[x].rank) st[x].parent = y;
  52.         else
  53.         {
  54.             st[y].parent = x;
  55.             st[x].rank++;
  56.         }
  57.         return true;
  58.     }
  59. };
  60. int main()  
  61. {
  62.     SetUnion s;
  63.     int n, m;
  64.     scanf("%d %d", &n, &m);
  65.     vector<int> v(n);
  66.     vector<vector<int> > adj(n);
  67.     for(int i = 0; i < n; i++) v[i] = i;
  68.     s.makeSet(v);
  69.     for(int i = 0; i < m; i++) {
  70.     	int u, v;
  71.     	scanf("%d %d", &u, &v);
  72.     	u--;v--;
  73.     	s.do_union(u,v);
  74.     	adj[u].push_back(v);
  75.     	adj[v].push_back(u);
  76.     }
  77.     vector< pair<int,int> > minmax;
  78.     dfs(adj,n,minmax);
  79.     int cnt = 0;
  80.     for(pair<int,int> &p : minmax) {
  81.     	int minval = p.first;
  82.     	int maxval = p.second;
  83.     	for(int i = minval; i <= maxval; i++)
  84.     		if(s.do_union(minval, i))
  85.     			cnt++;
  86.     }
  87.     printf("%d", cnt);
  88.     return 0;
  89. }
Success #stdin #stdout 0s 4364KB
comments (?)
stdin
copy 
14 8
1 2
2 7
3 4
6 3
5 7
3 8
6 8
11 12
stdout
copy 
1
https://ideone.com/7dRt3I
language:
C++14 (gcc 8.3)
created:
4 years 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!