WA in a graph problem even when my code is almost same as solution getting AC

I used DFS on each character of source string to see whether it can be converted into target string with given mappings.

This is my solution -
https://www.codechef.com/viewsolution/51309324

This is the similar solution getting all correct -
https://www.codechef.com/viewsolution/51272761

1 Like

Consider the test input:

1
aa
b
1
a->b

Further consider not using cout within solve and instead making solve return true or false, printing the appropriate string inside main e.g. (untested):

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5 + 5;
const long long MOD = 1e9 + 7;
const long long INF = 1e9;

int dfs(int u, int tar, vector<int> *adj, int vis[]) {
    if(u==tar) return 1;
    vis[u] = 1;
    for (auto v : adj[u]) {
        if (!vis[v]){
            if (dfs(v,tar,adj,vis)) return 1;
        }
    }
    return 0;
}

bool solve() {
    int m;
    vector<int> adj[MAX_N];
    string s, t; cin>>s>>t;
    cin>> m;
    for (int i = 0; i < m; i++) {
        string a; cin>>a;
        adj[a[0]-'a'].push_back(a[3]-'a');
    }
    if(s.length()!=t.length())
        return false;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]!=t[i])
        {
            int vis[28] = {0};
            if((dfs(s[i]-'a', t[i]-'a', adj, vis))!=1) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int tc;
    cin >> tc;
    for (int i = 1; i <= tc; i++) {
        // cout << "Case #" << t << ": ";
        cout << (solve() ? "YES" : "NO") << '\n';
    }
}

Completely sidesteps the bug you ran into here, and simplifies the code, too.

2 Likes

Thank you so much for helping me out!

2 Likes