# 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;
}
```