-
Notifications
You must be signed in to change notification settings - Fork 0
/
Articulation_point.cpp
130 lines (127 loc) · 3.39 KB
/
Articulation_point.cpp
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
#include<bits/stdc++.h>
#define pf printf
#define sc scanf
#define PI 2*acos(0.0)
#define fast ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define mem(a,b) memset(a, b, sizeof(a) )
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define MAX 1234567899
#define mod 1000000007
#define all(v) (v).begin(),(v).end()
#define vSort(v) sort(all(v))
#define maxSort(v) sort(all(v),greater<int>())
#define Unique(v) v.erase(unique(all(v)),v.end())
#define sqr(x) ((x)*(x))
#define qube(x) ((x)*(x)*(x))
#define deci(n) cout<<fixed<<setprecision(n)
#define sci(n) sc("%d",&(n))
#define scii(x,y) sc("%d %d",&(x),&(y))
#define scl(x) sc("%lld",&(x))
#define scll(x,y) sc("%lld %lld",&(x),&(y))
#define vi vector<int>
#define hi pf(" HI \n")
#define pp pair<int,int>
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define F first
#define S second
#define check(n,pos) (n & (1<<(pos)))
#define biton(n,pos) (n (1<<(pos)))
#define bitoff(n,pos) (n & ~(1<<(pos)))
typedef long long int lli;
typedef unsigned long long int ulli;
int dx4[] = { 0, 0, -1, 1 } ;
int dy4[] = { -1, 1, 0, 0 } ;
bool valid( int r, int c, int x, int y )
{
if( x >= 1 && x <= r && y >= 1 && y <= c ) return 1 ;
return 0 ;
}
using namespace std;
vi graph[200005];
int vis[200005];
int start[200005];
int par[200005];
int low[200005];
int AP[200005];
int val=0;
void tarjan(int u)
{
vis[u]=1;
val++;
start[u]=val;
low[u]=val;
int node_edge=0;
for(int i=0; i<graph[u].size(); i++)
{
int v = graph[u][i];
if(par[u]==v)
continue;
if(vis[v]==0)
{
node_edge++;
par[v]=u;
tarjan(v);
low[u] = min(low[u],low[v]);
if(par[u]== -1 && node_edge>1)
{
AP[u]=1;
}
if(par[u]!= -1 && low[v]>=start[u])
{
AP[u]=1;
}
}
else
{
low[u] = min(low[u],start[v]);
}
}
}
void Articulation_point(int node)
{
for(int i=1; i<=node; i++)
par[i] = -1;
for(int i=1; i<=node; i++)
{
if(vis[i]==0)
{
tarjan(i);
}
}
}
int main ()
{
int t;
cin >> t;
for(int cs=1; cs<=t; cs++)
{
int node,edge;
cin>> node >> edge;
int u,v;
for(int i=1; i<=edge; i++)
{
cin >> u >> v;
graph[u].pb(v);
graph[v].pb(u);
}
Articulation_point(node);
int ans=0;
for(int i=1; i<=node; i++)
{
ans+=AP[i];
cout << AP[i]<< " ";
}
cout <<endl;
cout <<"Case "<<cs <<": "<<ans <<endl;
for(int i=1; i<=node; i++)
{
vis[i]=0;
graph[i].clear();
start[i]=1;
AP[i]=0;
}
}
return 0;
}