CodeLibrary/Graph/Making Bridge Tree.cpp at master · sayedppqq/CodeLibrary · 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
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
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define  FIO        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define  Fileio     freopen("output.txt","w",stdout);freopen("input.txt","r",stdin);
#define  all(v)     v.begin(),v.end()
#define  rall(v)    v.rbegin(),v.rend()
#define  MEM(a,x)   memset(a,x,sizeof(a))
#define  SZ(v)      v.size()
#define  nl         "\n"
#define  bug        cout<<"bug"<<nl;
#define  pi         acos(-1.0)
#define  ll     long long
#define  pb     push_back
#define  mp     make_pair
#define  pii    pair< int,int >
#define  pll    pair< ll,ll >
#define  vii    vector< int >
#define  vll    vector< ll >
#define  vpi    vector< pii >
#define  vpl    vector<pll>
#define  MX     100005
#define  EPS    1e-12
#define  ss     second
#define  ff     first
using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset=tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

inline ll powr(int a,int b){ll res=1;while(b){if(b&1) res*=a;a*=a;b/=2;}return res;}
int cases=1;

#ifdef ppqq
     #define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template < typename Arg1 >
    void __f(const char* name, Arg1&& arg1){
        cerr << name << " is " << arg1 << std::endl;
    }
    template < typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names+1, ',');
        cerr.write(names, comma - names) << " is " << arg1 <<"  ";
        __f(comma+1, args...);
    }
#else
    #define debug(...)
#endif

///******************************************START******************************************

///Source : https://codeforces.com/blog/entry/83980

vector<pair<int,int>> adj[100005];
vector<int>bridge_tree[100005],in_time,low;
vector<pair<int,int>>edges;
vector<bool> vis;
bool isBridge[100005];
int timer,n,m,grp[100005],id;
void dfs(int u,int p)
{
    in_time[u]=low[u]=timer++;
    vis[u]=true;

    for(auto it: adj[u])
    {
        if(it.ff==p) continue;
        if(vis[it.ff])
            low[u]=min(in_time[it.ff],low[u]);
        else
        {
            dfs(it.ff,u);
            low[u]=min(low[u],low[it.ff]);
            if(low[it.ff]>in_time[u])
                isBridge[it.ss]=true;
        }
    }
}
void findBridges()
{
    in_time.assign(n+2,0);
    low.assign(n+2,0);
    vis.assign(n+2,false);
    timer=1;
    for(int i=1;i<=n;i++)
        if(!vis[i]) dfs(i,-1);
}
void dfs2(int u,int p)
{
    vis[u]=true;
    grp[u]=id;
    for(auto it: adj[u])
    {
        if(vis[it.ff] || isBridge[it.ss]) continue;  ///avoiding if its a bridge
        dfs2(it.ff,u);
    }
}
void givingGroupNumber()
{
    vis.clear();vis.assign(n+2,false);
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            id++;
            dfs2(i,-1);
        }
    }
}
void makeBridgeTree()
{
    findBridges();
    givingGroupNumber();

    for(int i=1;i<=m;i++)
    {
        if(isBridge[i])
        {
            bridge_tree[grp[edges[i-1].ff]].pb(grp[edges[i-1].ss]);
            bridge_tree[grp[edges[i-1].ss]].pb(grp[edges[i-1].ff]);
        }
    }
}
int main()
{
    FIO;
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++)
    {
        cin>>u>>v;
        adj[u].pb({v,i});
        adj[v].pb({u,i});
        edges.pb({u,v});
    }

    makeBridgeTree();

}