1 / 2
Jul 2021

Can anybody help me why I am getting WA using bipartite graph.
Is anything wrong in this implementation?

#include <bits/stdc++.h>
#define int long long
using namespace std;

bool vis[40005];
int col[40005];
bool ans;

void dfs(int source, int c, vector<int> adj[])
{
	vis[source] = 1;
	col[source] = c;
	for (auto child : adj[source])
	{
		if (!vis[child])
		{
			dfs(child, 1 - c, adj);
		}
		else
		{
			if (col[source] == col[child])
			{
				ans = false;
				return;
			}
		}
	}
}

void solve()
{
	ans = true;
	for (int i = 0; i < 40005; i++)
	{
		col[i] = 0;
		vis[i] = 0;
	}
	int n, m;
	cin >> n >> m;
	vector<int> adj[n + 1];
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (int i = 1; i <= n; i++)
	{
		if (!vis[i])
		{
			ans = true;
			dfs(i, 0, adj);
			if (!ans)
			{
				cout << "Scenario #1:\n";
				cout << "Suspicious bugs found!";
				return;
			}
		}
	}
	cout << "Scenario #2:\n";
	cout << "No suspicious bugs found!";
}

signed main(void)
{
	int t;
	cin >> t;
	while (t--)
	{
		solve();
		cout << endl;
	}

	return 0;
}
  • created

    Jul '21
  • last reply

    Jul '21
  • 1

    reply

  • 491

    views

  • 1

    user

Finally I got it accepted.
I was not printing output as per required format.
Scenario #current_test, I was not taking care of current_test counter.