Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #pragma GCC optimize("Ofast")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- //using namespace __gnu_pbds;
- using namespace std;
- typedef long long ll;
- //typedef complex<double> cp;
- #define PI 3.14159265358979323846
- ll MOD = 1000000007;
- 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() };
- mt19937 rng(seq);
- //typedef tree <ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
- const int N = 300000;
- vector<ll> g[N];
- vector<ll> anss;
- ll used[N];
- ll pr[N];
- ll h[N];
- ll dfs(ll v){
- used[v] = 1;
- ll hh = -1, hhh = h[v], lll = 0;
- for (auto i : g[v]){
- if (used[i] == 1 && pr[v] != i){
- hhh = min(hhh, h[i]);
- }
- else{
- if (!used[i]) {
- lll++;
- h[i] = h[v] + 1;
- pr[i] = v;
- ll t = dfs(i);
- hh = max(t, hh);
- hhh = min(t, hhh);
- }
- }
- }
- if (v != 0 && hh >= h[v]){
- anss.push_back(v);
- }
- if (pr[v] == -1){
- if (lll > 1){
- anss.push_back(0);
- }
- }
- return hhh;
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- ll n, m;
- cin >> n >> m;
- for (int i = 0; i < m; i++){
- ll u, v;
- cin >> u >> v;
- u--, v--;
- g[u].push_back(v);
- g[v].push_back(u);
- }
- ll kol = 0;
- for (int i = 0; i < n; i++){
- if (!used[i]) {
- pr[i] = -1;
- dfs(i);
- kol++;
- }
- }
- sort(anss.begin(), anss.end());
- cout << anss.size() << endl;
- for (auto i : anss){
- cout << i + 1 << endl;
- }
- //clock_t time;
- //time = clock();
- // while((double)(clock() - time)/CLOCKS_PER_SEC < 3.95) {
- // // rng() % n
- }
- /*
- * 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
- 001001000000000000000000000000000000010000100010000000000000110 * */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement