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!