fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. void dfsUtil(vector<int>&visit, vector<vector<int>>g, int s, int &count, int n){
  6. 	visit[s] = 1;
  7. 	count++;
  8. 	for(int i=1;i<=n;i++ ){
  9. 		if(g[s][i] && !visit[i])dfsUtil(visit, g, i, count, n);
  10. 	}
  11. }
  12.  
  13. void printInconveinence(vector<vector<int>>g, vector<pair<int,int>> roads, int n){
  14. 	vector<int> visited, forest, ans;
  15.  
  16. 	int count =0, j;
  17. 	for(int i=0; i<roads.size(); i++){
  18. 		int u = roads[i].first, v=roads[i].second;
  19. 		// cout<<endl<<u<<" "<<v<<endl;
  20. 		// removed the road
  21. 		g[u][v]=0;
  22. 		g[v][u]=0;
  23.  
  24. 		visited.resize(n+1,0);
  25. 		// checking for no of city in each island or forest
  26.  
  27. 		for(int s=1;s<=n; s++){
  28. 			count =0;
  29. 			if(!visited[s])dfsUtil(visited, g, s, count, n);
  30. 			// cout<<"s-> "<<s<<" - "<<count<<", ";
  31. 			if(count)forest.push_back(count);
  32. 		}
  33.  
  34. 		// if each city can be reached from every other city 
  35. 		if(forest.size()==1){
  36. 			ans.push_back(0);
  37. 		} else{
  38. 			int no=0;
  39. 			for(int j=0;j<forest.size();j++){
  40. 				for(int k=j+1;k<forest.size();k++ )no += forest[j]*forest[k];
  41. 			}
  42. 			ans.push_back(no);
  43. 		}
  44.  
  45. 		// reset values to check if another road is removed what is the inconvenience then
  46. 		forest.clear();
  47. 		visited.clear();
  48. 	}
  49.  
  50. 	for(int i=0; i<ans.size(); i++)cout<<ans[i]<<endl;
  51. }
  52.  
  53. int main() {
  54. 	int n , m;
  55. 	cin>>n>>m;
  56. 	vector<vector<int>> g(n+1, vector<int>(n+1,0));
  57. 	vector<pair<int,int>> roads;
  58. 	int u,v;
  59. 	for(int i=0;i<m;i++){
  60. 		cin>>u>>v;
  61. 		g[u][v]=1;
  62. 		g[v][u]=1;
  63. 		roads.push_back(make_pair(u,v));
  64. 	}
  65. 	printInconveinence(g, roads, n);
  66.  
  67. 	return 0;
  68. }
Success #stdin #stdout 0s 5644KB
comments (?)
stdin
copy 
4 5
1 2
3 4
1 3
2 3
1 4
stdout
copy 
0
0
4
5
6
https://ideone.com/MxLZMv
graph| road removed | print inconvenience
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!