Advertisement
Guest User

Untitled

a guest
Apr 25th, 2019
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.24 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #pragma GCC optimize("Ofast")
  3. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6. //using namespace __gnu_pbds;
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. //typedef complex<double> cp;
  11. #define PI 3.14159265358979323846
  12. ll MOD = 1000000007;
  13. seed_seq seq{ (uint64_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(), (uint64_t) __builtin_ia32_rdtsc(), (uint64_t) (uintptr_t) make_unique<char>().get() };
  14. mt19937 rng(seq);
  15. //typedef tree <ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  16.  
  17. const int N = 300000;
  18. vector<ll> g[N];
  19. vector<ll> anss;
  20. ll used[N];
  21. ll pr[N];
  22. ll h[N];
  23. ll dfs(ll v){
  24.     used[v] = 1;
  25.     ll hh = -1, hhh = h[v], lll = 0;
  26.     for (auto i : g[v]){
  27.         if (used[i] == 1 && pr[v] != i){
  28.             hhh = min(hhh, h[i]);
  29.         }
  30.         else{
  31.             if (!used[i]) {
  32.                 lll++;
  33.                 h[i] = h[v] + 1;
  34.                 pr[i] = v;
  35.                 ll t = dfs(i);
  36.                 hh = max(t, hh);
  37.                 hhh = min(t, hhh);
  38.             }
  39.         }
  40.     }
  41.     if (v != 0 && hh >= h[v]){
  42.         anss.push_back(v);
  43.     }
  44.     if (pr[v] == -1){
  45.         if (lll > 1){
  46.             anss.push_back(0);
  47.         }
  48.     }
  49.     return hhh;
  50. }
  51.  
  52. int main() {
  53.     ios::sync_with_stdio(0);
  54.     cin.tie(0);
  55.     cout.tie(0);
  56.     ll n, m;
  57.     cin >> n >> m;
  58.     for (int i = 0; i < m; i++){
  59.         ll u, v;
  60.         cin >> u >> v;
  61.         u--, v--;
  62.         g[u].push_back(v);
  63.         g[v].push_back(u);
  64.     }
  65.     ll kol = 0;
  66.     for (int i = 0; i < n; i++){
  67.         if (!used[i]) {
  68.             pr[i] = -1;
  69.             dfs(i);
  70.             kol++;
  71.         }
  72.     }
  73.     sort(anss.begin(), anss.end());
  74.     cout << anss.size() << endl;
  75.     for (auto i : anss){
  76.         cout << i + 1 << endl;
  77.     }
  78.     //clock_t time;
  79.     //time = clock();
  80. //    while((double)(clock() - time)/CLOCKS_PER_SEC < 3.95) {
  81. //    // rng() % n
  82. }
  83. /*
  84.  *  10 5 7 3 10 9 5 2 3 9 6 4 4 5 6 1 6 1 9 10 2 9 2 8 4 10 4 8
  85. 001001000000000000000000000000000000010000100010000000000000110 *  */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement