fork(1) download
  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
stdin
4 4
1 2
1 3
4 2
4 3
stdout
2