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;
}