Link to the question:
My logic:
form the graph with given mappings.
find all the strongly connected components(used Kosaraju’s algo) and make a compressed graph…
after that I’m doing a dfs from nodes which have degree = 1(in compressed graph)
noting down the in and out time for all nodes…
now going through the strings if the corresponding character at a index belong to same connected component then i can make a move…or else if the first character’s node is an ancestor of the other…then YES or else it’s not possible…
Saw the editorial…I know i have over killed the problem… But it will be really helpful for me if i can know where my code is going wrong…
ps : found the problem…it was while checking if there’s a path from one node to another in the condensed graph using in and out time…solved the problem by just doing a dfs in the condensed graph and checking for reachability .
@everule1 Can some one tell me how to efficiently check for reachability in an directed graph with just one dfs or bfs?
#include<bits/stdc++.h>
#define lld long long
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vii vector<int>
#define umap unordered_map
#define lb lower_bound
#define ub upper_bound
#define mod 1000000007
#define all(x) x.begin(),x.end()
#define sort1(x) sort(x,greater<int>())
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
namespace forever {
template<class type1,class type2>
inline istream &operator>>(istream &in,pair<type1,type2> &p)
{
in>>p.ff>>p.ss;
return in;
}
template<class type1,class type2>
inline ostream &operator<<(ostream &o,pair<type1,type2> &p)
{
o<<p.ff<<" "<<p.ss;
return o;
}
template<class type>
inline ostream &operator<<(ostream &o,vector<type> &v)
{
for(int i=0;i<v.size();i++)
o<<v[i]<<" ";
return o;
}
template<class type>
inline ostream &operator<<(ostream &o,set<type> &v)
{
for(int x: v)
o<<x<<" ";
return o;
}
template<class t>
inline istream &operator>>(istream &in,vector<t> &p)
{
for(auto & x : p)
in >> x;
return in;
}
int power(int x, int y,int p = mod) {
int res = 1;
x = x % p;
while (y > 0) {
if (y & 1)
res = (res*x) % p;
y = y>>1;
x = (x*x) % p;
}
return res;
}
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(pair<uint64_t,uint64_t> x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x.first + FIXED_RANDOM)^(splitmix64(x.second + FIXED_RANDOM) >> 1);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
}
using namespace forever;
vii adj[26] , rev[26] , compressed[26];
umap<int,bool,custom_hash> seen;
vii comp(26),in(26),out(26);
void dfs1(int v,stack<int> &s){
seen[v] = true;
for(int x: adj[v]){
if(!seen[x]){
dfs1(x,s);
}
}
s.push(v);
}
void dfs2(int v,int cc) {
seen[v] = true;
comp[v] = cc;
//cout << v << " ";
for(int x: rev[v]){
if(!seen[x]){
dfs2(x,cc);
}
}
}
void dfs3(int v,int& t){
in[v] = t++;
seen[v] = true;
for(int x: compressed[v]){
if(!seen[x])
dfs3(x,t);
}
out[v] = t++;
}
void init() {
for(int i=0;i<26;i++){
adj[i].clear();
rev[i].clear();
compressed[i].clear();
}
seen.clear();
comp.clear();
in.clear();
out.clear();
}
void test_cases(){
//cout << "********new tc*********\n";
string a,b;
int m,i;
cin >> a >> b >> m;
init();
while(m--){
string str;
cin >> str;
adj[str[0]-'a'].pb(str[3]-'a');
rev[str[3]-'a'].pb(str[0]-'a');
}
int nn = a.length() , mm = b.length();
if(nn!=mm){
cout << "NO\n";
return;
}
stack<int> s;
for(i=0;i<26;i++){
if(!seen[i] && adj[i].size() > 0){
dfs1(i,s);
}
}
seen.clear();
//cout << "$$$$$$$$$$$$$$$$$$$$$$\n";
int cnt = 0;
while(!s.empty()) {
int te = s.top();
s.pop();
if(!seen[te]){
cnt++;
dfs2(te,cnt);
//cout << "\n";
}
}
//cout << "****************************\n";
for(i=0;i<26;i++){
if(adj[i].size() == 0)
continue;
int te = comp[i];
for(int x: adj[i]){
if(comp[x] != te){
compressed[te].pb(comp[x]);
}
}
}
//cout << compressed << "\n";
seen.clear();
//cout << "heyyyyyyyyyy*****\n";
int ti = 0;
for(i=1;i<=cnt;i++){
if(!seen[i] && compressed[i].size()==1){
dfs3(i,ti);
}
}
//cout << "hiii**\n";
bool can = true;
for(i=0;i<nn;i++){
if(comp[a[i]-'a'] != comp[b[i]-'a']){
// if the characters belong to two different s.c.components then
// comp[a[i]] ---> comp[b[i]] path should exist
int sr = comp[a[i]-'a'];
int rs = comp[b[i]-'a'];
can &= (in[sr] < in[rs] && out[sr] > out[rs]);
}
}
if(can)
cout << "YES\n";
else
cout << "NO\n";
}
int32_t main()
{
fio;
#ifndef ONLINE_JUDGE
freopen("sip.txt","r",stdin);
freopen("sout.txt","w",stdout);
#endif
int t=1;
cin >> t;
while(t--){
test_cases();
}
return 0;
}
