fork download
copy 
  1. //vertex cover using bi partite
  2. #include<bits/stdc++.h>
  3. #define ll long long 
  4. #define pb push_back
  5. #define mp make_pair
  6. #define si(i) scanf("%d",&i)
  7. #define fs first
  8. #define sc second
  9. #define pii pair<int,int>
  10. #define psi pair<string,int>
  11. #define FOR(i,j,k) for(int i=j;i<k;i++)
  12. #define REP(i,k) for(int i=0;i<k;i++)
  13. #define FORR(i,j,k) for(int i=n;i>=k;i--)
  14. #define test(t) int t;si(t);while(t--)
  15. #define MOD 1000000007
  16. using namespace std;
  17. std::vector<int> v[100005];
  18. int color[100005];
  19. int bfs(int a){
  20. 	queue<int> q;
  21. 	q.push(a);
  22. 	color[a] = 0;
  23. 	while(!q.empty()){
  24. 		int f = q.front();
  25. 		q.pop();
  26. 		int l = v[f].size();
  27. 		REP(i,l){
  28. 			int p = v[f][i];
  29. 			if(color[p] == -1){
  30. 				color[p] = (color[f] == 1) ? 0 : 1;
  31. 				q.push(p);
  32. 			}
  33. 			else{
  34. 				if(color[p] == color[f])
  35. 					return 1;
  36. 			}
  37. 		}
  38. 	}
  39. 	return 0;
  40. }
  41. int main()
  42. {	
  43. 	//std::iostream::sync_with_stdio(false);
  44. 	int n,m;
  45. 	si(n);
  46. 	si(m);
  47. 	int a,b;
  48. 	memset(color,-1,sizeof(color));
  49. 	REP(i,m){
  50. 		si(a);
  51. 		si(b);
  52. 		v[a].pb(b);
  53. 		v[b].pb(a);
  54. 	}
  55. 	int flag = bfs(1);
  56. 	if(flag){
  57. 		printf("-1\n");
  58. 		return 0;
  59. 	}
  60. 	std::vector<int> v1,v2;
  61. 	FOR(i,1,n+1)
  62. 		if(color[i] == 0)
  63. 			v1.pb(i);
  64. 		else
  65. 			v2.pb(i);
  66. 	int l1 = v1.size();
  67. 	int l2 = v2.size();
  68. 	cout << l2 << endl;
  69. 	REP(i,l2)
  70. 		cout << v2[i] << " ";
  71. 	cout << endl;
  72. 	cout << l1 << endl;
  73. 	REP(i,l1)
  74. 		cout << v1[i] << " ";
  75. 	cout << endl;
  76. 	return 0;
  77. }
Success #stdin #stdout 0s 5028KB
comments (?)
stdin
copy 
3 3
1 2
2 3
1 3
stdout
copy 
-1
https://ideone.com/3bNfFy
language:
C++14 (gcc 8.3)
created:
7 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!