Spoj BUGLIFE - A Bug’s Life Solution

  Problem Link:  https://www.spoj.com/problems/BUGLIFE/en/

Solution in C++:

1. /// La ilaha illellahu muhammadur rasulullah
2. ///******Bismillahir-Rahmanir-Rahim******///
3. /// Abul Hasnat Tonmoy
4. /// Department of CSE,23rd batch
5. /// Islamic University,Bangladesh
6. ///**********ALLAH IS ALMIGHTY************///
7. #include <bits/stdc++.h>
8. using namespace std;
9. const int N = 1e5 + 2;
10. std::vector<int> g[N];
11. bool vis[N], col[N], ok;
12. void dfs(int u) {
13. vis[u] = true;
14. for (auto v : g[u]) {
15. if (!vis[v]) {
16. col[v] = col[u] ^ 1;
17. dfs(v);
18. } else {
19. if (col[u] == col[v]) {
20. ok = false;
21. }
22. }
23. }
24. }
25. int main() {
26. int t, k;
27. cin >> t;
28. for (k = 1; k <= t; k++) {
29. memset(vis, 0, sizeof(vis));
30. memset(col, 0, sizeof(col));
31. int n, m;
32. cin >> n >> m;
33. while (m--) {
34. int u, v;
35. cin >> u >> v;
36. g[u].push_back(v);
37. g[v].push_back(u);
38. }
39. ok = true;
40. for (int i = 1; i <= n; i++) {
41. if (!vis[i]) {
42. dfs(i);
43. }
44. }
45. printf("Scenario #%d:\n", k);
46. if (ok) {
47. cout << "No suspicious bugs found!\n";
48. } else {
49. cout << "Suspicious bugs found!\n";
50. }
51. for (int i = 1; i <= n; i++) g[i].clear();
52. }
53. }