-
Notifications
You must be signed in to change notification settings - Fork 1
/
ArticulationPoints
161 lines (140 loc) · 4.2 KB
/
ArticulationPoints
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
/*
. Always use boolean visited array for avoiding MLE
. Pass minimum arguments to the function to avoid MLE
. Pass by reference as much as possible to avoid TLE in some cases
. Always use unordered_map with custom hash to make the process as fast as possible
*/
#include <bits/stdc++.h>
// #include <ext/pb_ds/detail/standard_policies.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define loop(i,a,b) for(int i=(a);i<(b);i++)
#define hunt(i,a,b) for(int i=(a);i<=(b);i++)
#define lp(i,a,b) for(int i = a; i >= b; i--)
#define rep(i,n) for(int i = 0; i < n; i++)
#define int long long int
#define pb push_back
#define f first
#define s second
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define ld long double
#define all(x) begin(x),end(x)
void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";}
int Bexp(int a,int b){ int ret=1; for (;b;a=a*a,b>>=1) if (b&1) ret=ret*a; return ret; }
ll gcd(ll A , ll B)
{
if(B == 0)return A;
return gcd(B , A%B);
}
ll min(ll a , ll b){return a > b ? b : a;}
ll max(ll a , ll b){return a > b ? a : b;}
/*
int mod(a, b) {
c = a % b
return (c < 0) ? c + b : c
*/
int mod(int a, int b) {
return (((a % b) + b) % b);
}
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
//Always check odd-even using AND and never using MODULO
bool is_odd(int n) {
return n & 1 != 0;
}
//Faster map
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
//unordered_map<int,int, custom_hash> mp;
void The_Hawk_returns()
{
#ifndef vjudge
if (fopen("input.txt", "r"))
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
}
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
vector<int>disc, low, ap,parent;
vector<bool>vis;
int id=0;
int articulationPoints(vector<int>adj[],int u, int p){
int children=0;
low[u]=disc[u]=id++;
vis[u]=true;
for(auto v: adj[u]){
if(v == p)continue;
if(!vis[v]){
children++;
articulationPoints(adj,v,u);
low[u] = min(low[u],low[v]);
if(p != -1 and low[v] >= disc[u])
ap[u]=1;
}else{
low[u] = min(low[u],disc[v]);
}
}
return children;
}
void solve(int test){
int n,m;
cin >> n >> m;
vector<int>adj[n];
disc.resize(n);
low.resize(n);
ap.resize(n);
vis.resize(n);
for(int i=0;i<n;i++)vis[i]=false;
while(m--){
int a,b;
cin >> a >> b;
a--;
b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i=0;i<n;i++){
if(!disc[i])
ap[i] = articulationPoints(adj,i,-1)>1;
}
int c=0;
for(int i=0;i<n;i++)
if(ap[i])cout << i+1 << " ",c=1;
if(!c){
cout << "There is no articulation point!\n";
}
}
int32_t main(){
The_Hawk_returns();
int t=1;
//cin >> t;
for(int test=1;test<=t;test++){
solve(test);
}
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<" ms\n";
}