fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector< int > g[100005];	// contains graph
  6. vector< int > ccs[100005];	// contains connected component
  7. //int graph[100005][100005];
  8.  
  9. vector< bool > visited;
  10. int color[100005];			// contains color of each vertex
  11.  
  12. void bfs( int i, int j ){
  13.  
  14. 	queue< int > q;	q.push( i );
  15. 	visited[i]= true;
  16. 	color[i]= 0;
  17. 	ccs[j].push_back( i );
  18.  
  19. 	while( !q.empty() ){
  20.  
  21. 		int u= q.front(); q.pop();
  22.  
  23. 		for( int k= 0; k< g[u].size(); ++k ){
  24.  
  25. 			int v= g[u][k];
  26.  
  27. 			if( color[v]== -1 && !visited[v] ){
  28.  
  29. 				color[v]= 1 - color[u];
  30. 				visited[v]= true;
  31. 				ccs[j].push_back( v );
  32. 				q.push( v );
  33.  
  34. 			}
  35.  
  36. 		}
  37.  
  38. 	}
  39.  
  40. }
  41.  
  42. int main(){
  43.  
  44. 	int n, m;
  45. 	int cc= 0 ;
  46.  
  47. 	memset( color, -1, sizeof( color ) );
  48. 	//memset( graph, 0, sizeof( graph ) );
  49.  
  50. 	scanf( "%d%d", &n, &m );
  51.  
  52. 	visited.assign( n+1, 0 );
  53.  
  54. 	for( int i= 0; i< m; ++i ){
  55.  
  56. 		int x, y;
  57.  
  58. 		scanf( "%d%d", &x, &y );
  59.  
  60. 		//graph[x][y]= 1;
  61. 		//graph[y][x]= 1;
  62. 		g[x].push_back( y );
  63. 		g[y].push_back( x );
  64. 	}
  65.  
  66. 	int j= 0;
  67.  
  68. 	for( int i= 1; i<= n; ++i ){
  69. 		if( !visited[i] ){
  70. 			cc++;
  71. 			bfs( i, j );
  72. 			j++;
  73. 		}
  74. 	}
  75.  
  76. 	//for( int i= 1; i<= n; ++i )
  77. 	//	cout << color[i] << " ";
  78.  
  79. 	int b, r;
  80. 	b= r= 0;
  81.  
  82. 	for( int i= 0; i< cc; ++i ){
  83.  
  84. 		for( int j= 0; j< ccs[i].size(); ++j )
  85. 			if( color[ccs[i][j]] )
  86. 				r++;
  87. 			else
  88. 				b++;
  89. 	}
  90.  
  91. 	cout << ( r + b - 2 ) << endl;	// this is only no. of ways;
  92.  
  93. 	return 0;
  94. }
Success #stdin #stdout 0s 6016KB
comments (?)
stdin
copy 
4 4
1 2
1 3
4 2
4 3
stdout
copy 
2
https://ideone.com/9NWTm4
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!