New Reform | Editorial by ankitraj1996

So, this is an editorial for the problem **New Reforms** from codeforces round 346 Div. 2 and the problem is labelled as E. So it should be tough, but its easy-medium.

**Statement :-**
Berland has n cities connected by m bidirectional roads. No road connects a city to itself, and each pair of cities is connected by no more than one road. It is not guaranteed that you can get from any city to any other one, using only the existing roads.

The President of Berland decided to make changes to the road system and instructed the Ministry of Transport to make this reform. Now, each road should be unidirectional (only lead from one city to another).

In order not to cause great resentment among residents, the reform needs to be conducted so that there can be as few separate cities as possible. A city is considered separate, if no road leads into it, while it is allowed to have roads leading from this city.

Help the Ministry of Transport to find the minimum possible number of separate cities after the reform.

**Sample Test Case :-**
4 3
2 1
1 3
4 3

Here n=4 and m=3 i.e. nodes are from 1 to 4 and there are 3 edges in the graph.
![Sample test case](https://imgur.com/a/mPDaVs7)

Image link :- [Link](https://imgur.com/a/mPDaVs7)
As in the image we can see that, what the graph looks like.

**Solution :-**
Now our task it to find the minimum possible number of separate cities, so the best way is to divide the graph into **connected components** and then solve them separately.
For each connected components, we can solve it by choosing a vertex as the root, and then performing the **DFS** over the connected component. Now we can see that in
this case, the root of the connected component will be the only separate city, because no road leads to it and for all other nodes there must be an edge leading to it. Now there
may be a case when the **connected component is a cyclic one**, if this happens then there will be no separate cities, because if we start from the root then at the end on the **DFS**
we will end up on the root of the graph only.
So, the solution just comes down to the fact that it will be equal to the **number of connected components in the graph which are acyclic in nature** .

**Code :-**
```

/*
 * Ankit Raj, NIT Agartala
 */
#include<bits/stdc++.h>
using namespace std;
#define lld long long int
#define lim 100007
#define BOOST ios_base::sync_with_stdio(0) 
#define NITRO cin.tie(NULL)
#define pb push_back
#define mp make_pair
#define F first
#define S second
vector<vector<int>>graph(lim);
bool visited[lim];
bool cyclic_component;
void dfs(int src,int parent)
{
	visited[src] = true;
	for(auto child:graph[src])
	{
		if(!visited[child])
		{
			dfs(child,src);
		}
		else if(visited[child]==true && child!=parent)
		{
			cyclic_component = true;
			return;
		}
	}
}
int main()
{
	BOOST;
	NITRO;
	clock_t t1,t2;
	t1 = clock();
	/*
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	*/ 
	//Main Code
	int n,m;
	cin>>n>>m;
	int ans = 0;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		graph[u].pb(v);
		graph[v].pb(u);
	}
	memset(visited,false,sizeof(visited));
	for(int i=1;i<=n;i++)
	{
		if(!visited[i])
		{
			cyclic_component = false;
			dfs(i,-1);
			if(!cyclic_component)
			{
				ans++;
			}
		}
	}
	cout<<ans<<"\n";

t2 = clock();
	float diff = (float)t2 - (float)t1;
	float execution_time = diff/CLOCKS_PER_SEC;
	//cout<<"\n"<<execution_time;
	//system("pause");
}

```

New Reform | Editorial by ankitraj1996

Download submission

All caught up!

View submission

Is your resume even shortlisted?