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?