fork download
copy 
  1. #include "bits/stdc++.h"
  2.  
  3. using namespace std;
  4.  
  5. struct UF {
  6.     int N;
  7.     std::vector<int> e;
  8.     void init(int n){
  9.         e.assign(n,-1);
  10.     }
  11.     bool sameSet(int a, int b) { return find(a) == find(b); }
  12.     int size(int x) { return -e[find(x)]; }
  13.     int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
  14.     bool join(int a, int b) {
  15.         a = find(a), b = find(b);
  16.         if (a == b) return false;
  17.         if (e[a] > e[b]) swap(a, b);
  18.         e[a] += e[b]; e[b] = a;
  19.         return true;
  20.     }
  21. };
  22.  
  23. int32_t main(){
  24.  
  25.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  26.  
  27.     int n, m; cin>>n>>m;
  28.     UF dsu_for_graph_one, dsu_for_graph_two;
  29.     dsu_for_graph_one.init(n), dsu_for_graph_two.init(n);
  30.  
  31.     vector<int>degreeSeq_firstGraph(n), degreeSeq_secondGraph(n);
  32.     vector<int>componentSize_firstGraph, componentSize_secondGraph;
  33.  
  34.     for(int i = 0;i<m;i++){
  35.         int a, b; cin>>a>>b;
  36.         --a, --b;
  37.         degreeSeq_firstGraph[a]++, degreeSeq_firstGraph[b]++;
  38.         dsu_for_graph_one.join(a, b);
  39.     }
  40.  
  41.     for(int i = 0;i<m;i++){
  42.         int a, b; cin>>a>>b;
  43.         --a, --b;
  44.         degreeSeq_secondGraph[a]++, degreeSeq_secondGraph[b]++;
  45.         dsu_for_graph_two.join(a, b);
  46.     }
  47.  
  48.     for(int i = 0;i<n;i++){
  49.         componentSize_firstGraph.push_back(dsu_for_graph_one.size(i));
  50.         componentSize_secondGraph.push_back(dsu_for_graph_two.size(i));
  51.     }
  52.  
  53.     sort(degreeSeq_firstGraph.begin(), degreeSeq_firstGraph.end());
  54.     sort(degreeSeq_secondGraph.begin(), degreeSeq_secondGraph.end());
  55.     sort(componentSize_firstGraph.begin(), componentSize_firstGraph.end());
  56.     sort(componentSize_secondGraph.begin(), componentSize_secondGraph.end());
  57.  
  58.     if(degreeSeq_firstGraph == degreeSeq_secondGraph && componentSize_firstGraph == componentSize_secondGraph){
  59.         cout<<"Yes";
  60.     }
  61.     else cout<<"No";
  62.  
  63.  
  64.  
  65. }
Success #stdin #stdout 0.01s 5468KB
comments (?)
stdin
copy 
6 5
1 2
2 3
3 4
4 5
3 6
1 2
2 3
3 4
4 5
2 6
stdout
copy 
Yes
https://ideone.com/w01ouX
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!