PROBLEM LINK:
Author: freemancs
Tester: pulkit_0110
Editorialist: freemancs
DIFFICULTY:
MEDIUM.
PREREQUISITES:
Basic-obseravtions,dfs,Bridges
PROBLEM:
You have to find how many bi-directional edges can be converted to uni-directional edges without violating that each city has a way to reach every other city
EXPLANATION:
This problem can be easily solved by considering these Two cases
case - 1 (multiple edges between two particular cities):
In this case these edges can always be converted to unidirectional edges as you can redirect one edge in one direction and other edges in the other direction
case - 2(No Multiple edges between two particular cities)
In this case every edge which is a bridge cannot be considerd for barricading as if you consider it for barricading it will violate the conditions
(i.e, each city has a way to reach every other city)
so the answer is total edges - (bridges without any multiple edges)
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define x first
#define y second
using namespace std;
const int max_n = (int)2e5 + 3;
vector<int> adj[max_n] ,dfs_in , dfs_low;
vector<bool> vis;
map<pair<int,int> ,int> mult;
int cities,roads;
int timer = 0;
int bridges = 0;
set<pair<int,int>> included;
void dfs(int next , int parent){
vis[next] = true;
dfs_low[next] = dfs_in[next] = timer++;
for(auto it : adj[next]){
if(vis[it] == false){
dfs(it , next);
dfs_low[next] = min(dfs_low[next] , dfs_low[it]);
if(dfs_low[it] > dfs_in[next]){
bridges++;
included.insert({min(it,next) , max(it,next)});
}
}
else if(vis[it] == true && it != parent){
dfs_low[next] = min(dfs_low[next],dfs_in[it]);
}
}
}
int main(){
cin >> cities >> roads;
for(int i =0 ; i < roads;i++){
int u,v;
cin >> u >> v;
if(u == v)
assert(false);
adj[u].pb(v);
adj[v].pb(u);
int lesser = min(u,v);
int greater = max(u,v);
mult[{lesser,greater}] += 1;
}
vis.assign(cities+1 , false);
dfs_in.assign(cities+1 , -1);
dfs_low.assign(cities+1,-1);
dfs(1 , 1);
int ans = roads - bridges;
for(auto it : mult){
// is a bridge and a multi-edge
if(included.find({it.x.x,it.x.y}) != included.end() && it.y > 1){
ans += 1;
}
}
cout<<ans;
return 0;
}