WA in Ada Matrix(Graph Coloring problem)

help
, , ,
1

Hello Folks,
In this problem, one can apply 2-sat or graph coloring with dfs. I’ve used graph coloring solution as explained by @vijju123. The problem statement can be seen here ans my solution that is evaluated as WA is:-

#include <bits/stdc++.h>
#include <iostream>
#include <stdlib.h>
#define wl ll t;cin>>t;while(t--)
#define fr(a,b,c) for(ll a = b; a<c; a++)
#define mp make_pair
#define pb push_back
#define endl "\n"
#define ll long long int
#define ld long double
#define pi pair<ll , ll>
#define ull unsigned long long
#define ps(x,y) fixed<<setprecision(y)<<x
#define li long int
#define frs first
#define sec second
#define inf INT_MAX
#define ninf INT_MIN
#define ul unsigned long int
#define fast std::ios::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
const ll mod = 1e9 + 7;
const ll N = 1 << 10;
vector<pi> adj[N];
vector<ll> vis;
ll good;

void dfs(ll u, ll col)
{
	if (vis[u] != 0)
	{
		if (col != vis[u])
			good = 0;
		return;
	}

	vis[u] = col;
	for (auto v : adj[u])
	{
		dfs(v.frs, col * (v.sec));
	}
}

void solve()
{
	ll n;
	cin >> n;
	ll a[n][n], b[n][n];
	for (ll i = 0; i < n; i++)
		for (ll j = 0; j < n; j++)
			cin >> a[i][j];
	for (ll i = 0; i < n; i++)
		for (ll j = 0; j < n; j++)
			cin >> b[i][j];
	for (ll i = 0; i < n; i++)
	{
		for (ll j = 0; j < n; j++)
		{
			if (a[i][j] == a[j][i] && b[i][j] == b[j][i] && a[i][j] == b[i][j])
				continue;
			if (a[i][j] == b[i][j] && a[j][i]==b[j][i])
			{
				adj[i].pb(mp(j, 1));
				adj[j].pb(mp(i, 1));
				continue;
			}
			if (a[i][j] == b[j][i] && a[j][i] == b[i][j])
			{
				adj[i].pb(mp(j, -1));
				adj[j].pb(mp(i, -1));
				continue;
			}

			cout << "No" << endl;
			for (ll h = 0; h < N; h++)
				adj[h].clear();
			return;
		}
	}

	good = 1;
	for (ll i = 0; i < N; i++)
		vis.pb(0);
	for (ll i = 0; i < n; i++)
	{
		if (vis[i])
			continue;
		dfs(i, 1);
	}

	if (good)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;

	for (ll i = 0; i < N; i++)
		adj[i].clear();
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	fast
	wl
	{
		solve();
	}
	return 0;
}

Can someone help me find the bug especially @vijju123.
Thanks in advance :blush: