Competetive-Code-Learns/articulation_points.cpp at master · RohanGoyal2014/Competetive-Code-Learns · GitHub

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
/*
 * Articulation Points in a graph
 * Link:https://www.hackerearth.com/practice/algorithms/graphs/articulation-points-and-bridges/practice-problems/algorithm/rhezo-and-destructive-mind/
 * Reference of already visited condition part: https://www.quora.com/q/competitiveprogramming2/Cut-Vertex-Articulation-point
 * For tutorial refer to GFG,Tushar Roy and William Fiset
 *
 * */

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mkp(a,b) make_pair(a,b)
#define eb emplace_back
#define mod (long long)(1e9+7)
#define FILE_READ freopen("input.txt","r",stdin)
#define FILE_WRITE freopen("output.txt","w",stdout)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long ul;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int currTime=0;
set<int> articulationPoints;
void dfs(int root,int parent,bool visited[],int low[],int disc_time[],vector<int> nbs[])
{
    visited[root]=true;
    low[root]=disc_time[root]=currTime;
    ++currTime;
    int child=0;
    for(auto i:nbs[root])
    {
        if(i==parent)
        {
            continue;
        }
        if(!visited[i])
        {
            // incrementing child inside visited[i]==false block so that
            // only independent children are counted which are dependent on current node
            // for connectivity
            child++;
            dfs(i,root,visited,low,disc_time,nbs);
            low[root]=min(low[root],low[i]);
            if(parent==-1 && child>=2)
            {
                articulationPoints.insert(root);
            }
            else if(parent!=-1 && disc_time[root]<=low[i])
            {
                //implies that back edge does not exist
                articulationPoints.insert(root);
            }
        }
        else
        {
            low[root]=min(low[root],disc_time[i]);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
//    FILE_READ;
//    FILE_WRITE;

    int n,m;
    cin>>n>>m;
    vector<pii> edges(m);
    vector<int> nbs[n];
    int disc_time[n],low[n];
    bool vis[n]={0};
    for(int i=0;i<m;++i)
    {
        cin>>edges[i].first>>edges[i].second;
        edges[i].first--;
        edges[i].second--;
        nbs[edges[i].first].eb(edges[i].second);
        nbs[edges[i].second].eb(edges[i].first);
    }
    //looping because the graph may be disconnected iniatially
    for(int i=0;i<n;++i)
    {
        if(!vis[i])
        dfs(i, -1, vis, low, disc_time, nbs);
    }

    int q;
    cin>>q;
    while(q--)
    {
        int x;
        cin>>x;
        x--;
        if(articulationPoints.find(x)==articulationPoints.end())
        {
            cout<<"Not Satisfied\n";
        }
        else
        {
            cout<<"Satisfied "<<nbs[x].size()<<"\n";
        }
    }

    return 0;
}