 # PRTWHY-EDITORIAL

Author: freemancs
Tester: pulkit_0110
Editorialist: freemancs

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<bool> vis;

map<pair<int,int> ,int> mult;

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++;

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(){

for(int i =0 ; i < roads;i++){
int u,v;
cin >> u >> v;

if(u == v)
assert(false);

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;
}
``````
1 Like

why the answer is not simply

``````Edges - Number of vertex whose in-degree is 1
``````

?
@maesterr @freemancs