fork(3) download 
  1. /*
  2. * @problem: 
  3. */
  4.  
  5. #include <iostream>
  6. #include <cstring>
  7. #include <cstdio>
  8. #include <iomanip>
  9. #include <cmath>
  10. #include <limits.h>
  11. #include <vector>
  12. #include <map>
  13. #include <bitset>
  14. #include <string>
  15. #include <iterator>
  16. #include <set>
  17. #include <utility>
  18. #include <queue>
  19. #include <numeric>
  20. #include <functional>
  21. #include <ctype.h>
  22. #include <stack>
  23. #include <algorithm>
  24. #include <cstdlib>
  25. #define MAX 100100
  26. #define mod 1000000007LL
  27. #define bitcnt(x) __builtin_popcountll(x)
  28. #define MS0(x) memset(x, 0, sizeof(x))
  29. #define MS1(x) memset(x, -1, sizeof(x))
  30. #define ll long long int
  31. #define mp(x, y) make_pair(x, y)
  32. #define pii pair<int, int>
  33. #define pll pair<ll, ll>
  34. #define in(x) scanf("%lld", &x)
  35. #define ind(x) scanf("%d", &x)
  36. #define ins(x) scanf("%s", x)
  37. #define pr(x) printf("%lld\n", x)
  38. #define prd(x) printf("%d\n", x)
  39. #define pi acos(-1.0)
  40. #define ff first
  41. #define ss second
  42.  
  43. using namespace std;
  44. int n, m, color[210], in[210], d, D;
  45. vector<int> v[210];
  46.  
  47. bool dfs(int src, int par) {
  48. 	if (color[src] == -1)
  49. 		color[src] = 1 - color[par];
  50. 	else if (color[src] == color[par])
  51. 		return 0;
  52. 	else return 1;
  53. 	bool ans = 1;
  54. 	for (int i : v[src]) {
  55. 		if (i != par)
  56. 			ans = (ans & dfs(i, src));
  57. 	}
  58. 	return ans;
  59. }
  60.  
  61. int main() {
  62. 	#ifdef LOCAL_PROJECT
  63. 		freopen("output1.txt", "r", stdin);
  64. 		// freopen("../output.txt", "w", stdout);
  65. 	#endif
  66.  
  67. 	while (cin >> n) { // taking input till EOF
  68. 		if (n == -1) {
  69. 			continue; // if no graph given as input
  70. 		}
  71. 		cin >> m >> d >> D;
  72. 		int a, b;
  73. 		bool flag = 0; // flag = 1 implies graph is not correct
  74. 		for (int i = 0; i < m; i++) {
  75. 			cin >> a >> b;
  76. 			if (a > n || b > n || a < 1 || b < 1) // checking if the node number is in the range or not
  77. 				flag = 1;
  78. 			b += n; // renaming vertices of 2nd set as n + 1, n + 2, ... , n + n
  79. 			v[a].push_back(b); // constructing adjacency list
  80. 			v[b].push_back(a);
  81. 		}
  82. 		MS1(color);
  83. 		color[0] = 1;
  84. 		for (int i = 1; i <= 2 * n; i++) {
  85. 			if(color[i] == -1) {
  86. 				if (!dfs(i, 0)) // checking if graph is bi-partite or not
  87. 					flag = 1;
  88. 			}
  89. 		}
  90. 		for (int i = 1; i <= 2 * n; i++) {
  91. 			if (v[i].size() < d || v[i].size() > D) { // checking if degree of each vertex is >= d and <= D
  92. 				flag = 1;
  93. 			}
  94. 			v[i].clear(); // resetting the adjacency list
  95. 		}
  96. 		if (flag)
  97. 			cout << "incorrect\n" << endl;
  98. 	}
  99. 	return 0;
  100. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/wm8EzY
language:
C++14 (gcc 8.3)
created:
8 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!