 # WA on Liars and Truth Tellers (Old Bronze problem)

Here is the link to the problem: http://usaco.org/index.php?page=viewproblem2&cpid=225.

I understand that the problem uses DFS. I understand the implication of “x y T” and “x y L” in terms of graphs (the former has x and y of the same color, while the latter corresponds to different colors). My attempt tries to check if the first i entries are consistent while taking in the adjacencies one-by-one. I believe it should work because I call DFS on all components in the works() function and implements the DFS just like a standard bipartiteness check. Note also that I use an adjacency matrix.

However, my code only passes the sample input and gets a WA on everything else. I tried to debug, but the implementation of bipartiteness check is standard, and I was not able to find any bugs.

My code is here: Liars and Truth Tellers

``````#include <bits/stdc++.h>

using namespace std;

const int MX = 1e3;

int n, m;
char adj[MX][MX];
vector<int> vis(MX), color(MX);

bool bad;
void dfs(int u, bool c){
vis[u] = 1;
for(int v=0; v<n; ++v) if(adj[u][v]!='\0'){
bool nc = (adj[u][v]=='T' ? c : !c);
if(!vis[v]) dfs(v,nc);
else if(color[v]!=nc) bad = 1;
}
}

bool works(){
bad = 0;
fill(vis.begin(), vis.end(), 0);
fill(color.begin(), color.end(), 0);
for(int i=0; i<n; ++i){
if(!vis[i]) dfs(i,0);
if(bad) return false;
}
return true;
}

int main()
{
// freopen("truth.in", "r", stdin);
// freopen("truth.out", "w", stdout);
cin >> n >> m;
//    for(int r=0; r<n; ++r){
//        for(int c=0; c<n; ++c){
//            adj[r][c] = '_'; // indicator that [r][c] is blank
//        }
//    }
for(int i=0; i<m; ++i){
int a, b; char c;
cin >> a >> b >> c;
a--, b--;
adj[a][b] = c;
if(!works()){
cout << i << '\n';
exit(0);
}
}
cout << m << '\n';
}
``````

Can you please help me? Thank you!

Hi, can you please respond?

The second test case doesn’t seem to hard to debug. Have you tried downloading the test data?