In this HackerEarth Edges on a path problem solution Given a connected graph with n nodes and m edges, where m <= n.You are also given two nodes a and b of the graph.
You need to find the number of edges which are present in all paths between a and b.
HackerEarth Edges on a path problem solution.
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ratio>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <climits>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define in insert
#define vll vector<ll>
#define endl "\n"
#define pll pair<ll,ll>
#define f first
#define s second
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define int ll
#define sz(x) (ll)x.size()
#define all(x) (x.begin(),x.end())
using namespace std;
const ll INF = 1e12;
const ll N =(1e5+5); // TODO : change value as per problem
const ll M = (3e5+5);
const ll MOD = 1e9+7;
vll graph[N];int U[M],V[M];//edge list representation of input graph
vll tree[N];//Bridge Tree formed from the given graph
bool isbridge[M]; // if i'th edge is a bridge edge or not
int vis[N],arr[N],T,cmpno;//supporting stuff
queue<int> Q[N];
int nice[N];
int adj(int u,int e){
return U[e]==u?V[e]:U[e];
}
int dfs0(int u,int edge)//mark bridges
{
int dbe = arr[u] = T++;
vis[u]=1;
for(int i=0;i<graph[u].size();i++)
{
int e = graph[u][i];
int w = adj(u,e);
if(!vis[w])
dbe = min(dbe,dfs0(w,e));
else if(e!=edge)
dbe = min(dbe,arr[w]);
}
if(dbe == arr[u] && edge!=-1)
isbridge[edge]=true;
return dbe;
}
void dfs1(int v) //Builds the tree with each edge a bridge from original graph
{
int currcmp = cmpno; // current component no.
Q[currcmp].push(v);// A different queue for each component, coz during bfs we shall go to another component (step of dfs) and then come back to this one and continue our bfs
vis[v]=1;
nice[v] = currcmp;
while(!Q[currcmp].empty()) //bfs. Exploring all nodes of this component
{
int u = Q[currcmp].front();
Q[currcmp].pop();
for(int i=0;i<graph[u].size();i++)
{
int e = graph[u][i];
int w = adj(u,e);
if(vis[w])continue;
nice[w] = currcmp;
if(isbridge[e]) //if the edge under consideration is bridge and other side is not yet explored, go there (step of dfs)
{
cmpno++;
tree[currcmp].push_back(cmpno);
tree[cmpno].push_back(currcmp);
dfs1(w);
}
else //else continue with our bfs
{
Q[currcmp].push(w);
vis[w]=1;
}
}
}
}
void solve(){
int n,m;
cin >> n >> m;
int a,b;
cin >> a >> b;
a--;
b--;
for(int i= 0;i<m;i++){
int u,v;
cin >> u >> v;
u--;
v--;
U[i] = v;
V[i] = u;
graph[u].pb(i);
graph[v].pb(i);
}
dfs0(0,-1);
memset(vis,0,sizeof(vis));
dfs1(0);
int u = nice[a];
int v = nice[b];
queue<int> q;
vector<int> dis(cmpno+1,-1);
dis[u] =0;
q.push(u);
while(!q.empty()){
int p = q.front();
q.pop();
for(auto g:tree[p]){
if(dis[g] == -1){
dis[g] = dis[p] + 1;
q.push(g);
}
}
}
cout << dis[v] << endl;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
// freopen(".in","r",stdin);freopen(".out","w",stdout);
ll tt=1;
// cin >> tt;
while(tt--){
solve();
}
}
Second solution
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
template <class T, class L> inline bool smax(T &x, L y){ return x < y ? ( x = y, 1) : 0; }
template <class T, class L> inline bool smin(T &x, L y){ return y < x ? ( x = y, 1) : 0; }
typedef pair <int, int> pii;
typedef long long ll;
const int maxn = 1e5 + 17, lg = 17, mod = 1e9 + 7;
int n, m, q, edge[maxn], comp[maxn], h[maxn], gp, cnt[maxn], po[maxn], par[maxn][lg];
bool bl[maxn], seen[maxn], is[maxn];
vector<int> g[maxn];
pii e[maxn];
int hi(int v = 0, int p = -1){
int ret = h[v];
seen[v] = 1;
for(auto i : g[v]){
int u = edge[i] ^ v;
if(!seen[u]){
h[u] = h[v] + 1;
int t = hi(u, v);
if(t == h[u]) bl[i] = 1;
smin(ret, t);
}
else if(u != p) smin(ret, h[u]);
}
return ret;
}
void hello(int v){
cnt[ comp[v] = gp ]++;
for(auto i : g[v]){
int u = edge[i] ^ v;
if(!bl[i] && comp[u] == -1)
hello(u);
}
}
void dfs(int v = 0){
for(int i = 1; i < lg; i++) par[v][i] = par[ par[v][i - 1] ][i - 1];
for(auto u : g[v])
if(u != par[v][0]){
h[u] = h[v] + 1, par[u][0] = v;
cnt[u] += cnt[v];
dfs(u);
}
}
int lca(int v, int u){
if(h[v] > h[u]) swap(v, u);
for(int i = 0; i < lg; i++)
if(h[u] - h[v] >> i & 1)
u = par[u][i];
for(int i = lg - 1; i >= 0; i--)
if(par[v][i] != par[u][i])
v = par[v][i], u = par[u][i];
return v == u ? v : par[v][0];
}
void build_tree(){
fill(g, g + n, vector<int>());
for(int i = 0; i < m; i++)
if(bl[i])
g[ comp[ e[i].X ] ].push_back(comp[ e[i].Y ]),
g[ comp[ e[i].Y ] ].push_back(comp[ e[i].X ]);
dfs();
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
for(int i = po[0] = 1; i < maxn; i++) po[i] = (po[i - 1] << 1) % mod;
cin >> n >> m;
int a, b;
cin >> a >> b;
a--, b--;
for(int i = 0, v, u; i < m; i++){
cin >> v >> u, v--, u--;
edge[i] = v ^ u, e[i] = {v, u};
g[v].push_back(i), g[u].push_back(i);
}
hi();
memset(comp, -1, sizeof comp);
for(int i = 0; i < n; i++)
if(comp[i] == -1){
hello(i);
cnt[gp] = is[gp] = cnt[gp] - 1;
gp++;
}
build_tree();
cout << h[comp[a]] + h[comp[b]] - 2 * h[lca(comp[a], comp[b])] << '\n';
return 0;
cin >> q;
for(int v, u; q--; ){
cin >> v >> u, v--, u--;
v = comp[v], u = comp[u];
int p = lca(v, u);
cout << po[ cnt[v] + cnt[u] - 2 * cnt[p] + is[p] ] << '\n';
}
return 0;
}
0 Comments