fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // bfs
  5. const int maxN=1e5;
  6. int N, M, a, b;
  7. long long int ans=0;
  8. bool sym=true;
  9. vector<int> to[maxN+1];
  10. int clr[maxN+1]; // color  : 0(empty), 1, 2
  11. deque<int> dq;
  12.  
  13. void bfs(int v){
  14. 	int Na=0;
  15. 	int Nb=0;
  16. 	dq.push_back(v);
  17. 	clr[v]=1;
  18. 	Na++;
  19.  
  20. 	while( !dq.empty() ){
  21. 		int now=dq.front();
  22. 		dq.pop_front();
  23.  
  24. 		for(int i=0;i<to[now].size();i++){
  25. 			int nxt=to[now][i];
  26. 			if( clr[nxt]==clr[now] )
  27. 				sym=false;
  28. 			if( clr[nxt]==0 ){
  29. 				if( clr[now]==1 ){
  30. 					clr[nxt]=2;
  31. 					Nb++;
  32. 				}
  33. 				else{
  34. 					clr[nxt]=1;
  35. 					Na++;
  36. 				}
  37. 				dq.push_back(nxt);
  38. 			}
  39.  
  40.  
  41. 		}
  42. 	}
  43. 	ans+=min(Na,Nb);
  44. }
  45.  
  46. int main() {
  47. 	ios::sync_with_stdio(0);
  48. 	cin.tie(0); cout.tie(0);
  49. 	cin>>N>>M;
  50.  
  51. 	for(int i=0;i<N;i++)
  52. 		clr[i]=0;
  53.  
  54. 	for(int i=0;i<M;i++){
  55. 		cin>>a>>b;
  56. 		to[a].push_back(b);
  57. 		to[b].push_back(a);
  58. 	}
  59. 	for(int i=1;i<=N;i++){
  60. 		if( clr[i]==0 )
  61. 			bfs(i);
  62. 	}
  63. 	if( sym ) cout<<ans;
  64. 	else cout<<0;
  65.  
  66. }
Success #stdin #stdout 0.01s 5876KB
comments (?)
stdin
copy 
13 12
8 7
1 2
3 6
5 4
1 3
9 8
11 12
10 8
6 5
3 4
6 2
13 12
stdout
copy 
5
https://ideone.com/4KGQME
c889. 2. 二分圖 -- 107學年度全國資訊學科能力競賽
language:
C++14 (gcc 8.3)
created:
1 year 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!