# CAGHS - EDITORIAL

**URL:** <https://discuss.codechef.com/t/caghs-editorial/85459>\
**Category:** editorial\
**Tags:** depth-first-search, graphs, kosaraju, medium, strongly-connected-components, topological-sort\
**Created:** [February 13, 2021, 5:03pm UTC](https://discuss.codechef.com/t/caghs-editorial/85459 "2021-02-13T17:03:56Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![gigaliths](https://discuss.codechef.com/user_avatar/discuss.codechef.com/gigaliths/32/121603_2.png) [@gigaliths](https://discuss.codechef.com/u/gigaliths)\
**Post date:** [February 13, 2021, 5:03pm UTC](https://discuss.codechef.com/t/caghs-editorial/85459/1 "2021-02-13T17:03:56Z")

</div>

# PROBLEM LINK:

[Problemset - CAGHS](https://www.codechef.com/ACRN2021/problems/CAGHS)  
[AC-RUN Contest Link](https://www.codechef.com/ACRN2021)

_ **Author:** _[Hardik](https://www.codechef.com/users/hardik_kapoor), [Ganesh](https://www.codechef.com/users/ganesh_1085) , [Shobit](https://www.codechef.com/users/gigaliths).  
_ **Tester:** _[Hardik](https://www.codechef.com/users/hardik_kapoor), [Ganesh](https://www.codechef.com/users/ganesh_1085) , [Shobit](https://www.codechef.com/users/gigaliths).  
_ **Editorialist:** _[Shobit](https://www.codechef.com/users/gigaliths).

# DIFFICULTY:

MEDIUM

# PREREQUISITES:

Graphs , DFS , Strongly Connected Components (Kosarajus Algorithm) , Topological Sort

# PROBLEM:

Basically , we have been given a directed graph and we have to add edges into this graph such that every node is reachable from at least one of the hospital nodes. Each edge added from u to v costs C(v) . We have to add edges optimally so that total cost can be minimized.

# EXPLANATION:

1. It’s always optimal to add the edges directly from some hospital to a node which is Bad.

2. If there are two nodes u , v. If u is good and there is an edge from u to v , then v is also good. Similarly there will be components of such Bad nodes as well.

3. Let’s assume for now that the given graph is always a DAG

4. Now how will we approach in case of a general directed graph ?

 ![image](https://s3.amazonaws.com/discourseproduction/original/3X/6/9/698e753d5d794c24b66379cb749897d8678dd0f5.png)

 ![image](https://s3.amazonaws.com/discourseproduction/original/3X/8/1/81cf57bcba036dfc58b6ecf1a428990926cfb316.png)

 ![image](https://s3.amazonaws.com/discourseproduction/original/3X/0/d/0d7d0d04d6c811e3868872839822d636e18dbba9.png)

# SOLUTIONS:

> **Editorialist's Solution**
>
> ```
> #include<bits/stdc++.h>
> using namespace std;
> #define ll long long
> #define int ll
> #define debug(v) cout << ">>" << #v << ':' << v << endl;
> #define endl "\n"
> #define pb push_back
> #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
> #define umap unordered_map
> #define pii pair<int , int>
> #define all(v) v.begin() , v.end()   
> #define ld long double
> #define min3(a,b,cost) min(a,min(b,cost))
> #define min4(a,b,cost,d ) min(a , min(b , min(cost,d)))
> #define max3(a,b,cost) max(a , max(b,cost))
> #define max4(a,b,cost,d) max(max(a,b) , max(cost,d))
> #define vi vector<int>     
> #define x first
> #define y second 
> #define dbg(a,b) cout<<a<<" "<<b<<endl;   
> #define mk make_pair  
> #define rep(i,j,n) for(int (i)=(j) ; i<(n) ; i++)                       
> #define pq priority_queue
> #define mn(v) *min_element(all(v))
> #define mx(v) *max_element(all(v));
> void reader()
> {
> #ifndef ONLINE_JUDGE
> // for getting input from input.txt
> freopen("input.txt", "r", stdin);
> freopen("output.txt" , "w" , stdout);
> #endif
> }
> const int MOD = 1e6;
> const int N = 2e5+10;
> const int inf = 1e18;
> ///////////////////////////////////////template ends here :
> int n , m;
> vector<int> adj[N] , g[N]; // Adj is the normal graph and G is reversed graph.
> bool vis[N];
> stack<int> path; // stores the nodes as per finishing time of dfs in given graph.
> int h[N]; // Stores the costs of each node , zero if hospital.
> int C[N]; // stores component id of each node in condensed graph.
> int cnt=0; // for keeping track of number of components in condensed graph.
> void dfs( int u )
> {
> vis[u] = true;
> for(auto i : adj[u])
> {
> if(!vis[i])dfs(i);
> }
> path.push(u); // stores as per the finishing time.
> }
> // Run dfs on reversed graph in reverse order of finishing time obtained in dfs on normal graph.
> void scc( int u)
> {
> vis[u] = true;
> C[u] = cnt;
> for(auto i : g[u])
> {
> if(!vis[i])scc(i);
> }
> }
> void solve()
> {
> cin>>n>>m;
> for(int i=0 ; i<m ; i++)
> {
> int u , v;
> cin>>u>>v;
> adj[u].pb(v); //Normal graph.
> g[v].pb(u); // Reversed graph.
> }
> for(int i=0 ; i<n ; i++)cin>>h[i]; // Node_cost , zero if hospital.
> for(int i=0 ; i<n ; i++) // DFS on given graph.
> {
> if(vis[i] == 0)dfs(i);
> }
> for(int i=0 ; i<n ; i++)vis[i] = 0;
> 
> // Kosarajus Algorithm of finding SCC.
> while(path.size() > 0) // dfs on reverse graph with obtained finishing times. 
> {
> if(!vis[path.top()] )
> {
> scc(path.top());
> cnt++;
> }
> path.pop();
> }
>    
> // After obtaining strongly connected components :- 
> vector<int> indegree(cnt , 0); //stores indegree of each component
> vector<int> has_H(cnt , 0); //stores if there is hospital in a component
> vector<int> Min_node(cnt , inf); //stores the min_cost node in each component.
> for(int i=0 ; i<n ; i++)
> {
> if(h[i] == 0) //if there is hospital in component
> {
> has_H[C[i]] = 1;
> }
> else //updation of min_cost node of each component.
> {
> Min_node[C[i]] = min(Min_node[C[i]] , h[i]);
> }
> for(auto j : adj[i]) //Update indegree if cross component edges exist.
> {
> if(C[j] != C[i])
> indegree[C[j]]++;
> }
> }
> int ans=0;
> for(int i=0 ; i<cnt ; i++) // iterate through all components. [cnt == number of components]
> {
> // add cost of those components which doesnt have a hospital in them and have indegree 0.
> if(indegree[i] == 0 && has_H[i] == 0)
> {
> ans += Min_node[i];
> }
> }
>    
> cout<<ans<<endl;
> // Expected Time complexity O(N+M). 
> // O(N+M) for first DFS
> // O(N+M) for reverse second dfs.
> // O(N) for updating component details and finding answer.
>    
> }
> signed main() 
> {
> IOS
> //reader();  
> solve();
> }
> 
> ```