PROBLEM LINK:
Author: Akash Kumar Bhagat
Tester: Sandeep Singh,Arnab Chanda
Editorialist: Akash Kumar Bhagat
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Graph Traversal, Breadth-First-Search, Depth-First-Search
PROBLEM:
You are given a network of people related or came into contact with each other after the lockdown was imposed. You have 2 characters(which may or may not be the part of the network) and one of them has recently tested positive of Covid-19. Your task is to find whether there is a possibility of the other person getting infected or not(Supposing each and everyone who directly or indirectly came into contact with the infected person may be infected).
EXPLANATION:
Given the name of the infected person, we have to check whether there is a chance of the other person getting infected or not. We could analyse the network/graph of people who came into contact with each other, and traverse the network from the infected person (if he/she is present in the network) and check whether we encounter the other person on our way or not.
We may use any graph traversal technique either BFS or DFS and will get the desired result. In case the infected person id not in the graph, that means no one in the network came into contact with the infected person hence all other people including the other person is safe.
SOLUTIONS:
Python 3.7
def chk(graph,javed,mohan):
q=[javed]
visited={};boo=False
for i in graph.keys():
visited[i]=False
visited[j]=True
while(len(q)>0):
v=q[0];q.pop(0)
if(v==mohan):
return True
for i in graph[v]:
if(not visited[i]):
visited[i]=True
q.append(i)
return False
for _ in range(int(input())):
n,j,m=input().split();n=int(n)
dic={}
dic[j]=[];dic[m]=[]
for i in range(n):
a,b=input().split()
#print(a,b)
if(a in dic.keys()): dic[a].append(b)
else: dic[a]=[b]
if(b in dic.keys()): dic[b].append(a)
else: dic[b]=[a]
#print(dic)
ans="Quarantine" if(chk(dic,j,m)) else "Stay Home, Stay Safe"
print(ans)
CPP
#include <bits/stdc++.h>
#define ll long long int
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define scanarr(a,b,c) for( i=b;i<c;i++)cin>>a[i]
#define showarr(a,b,c) for( i=b;i<c;i++)cout<<a[i]<<' '
#define ln cout<<'\n'
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mod 1000000007
#define MAX 100005
using namespace std;
class dsu {
public:
vector <int> p;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
return true;
}
return false;
}
};
////////////////////////////////////////////////////////////////CODE STARTS HERE////////////////////////////////////////////////////////////////
vector <string> ans = {"Stay Home, Stay Safe", "Quarantine"};
unordered_map<string, int> mp;
void solve(){
int n, i, j;
string x, y, a, b;
mp.clear();
set <string> st;
cin >> n >> x >> y;
st.insert(x);
st.insert(y);
vector<pair<string, string>> joins;
for(i = 0 ; i < n; i++){
cin >> a >> b;
st.insert(a); st.insert(b);
joins.push_back({a, b});
}
dsu dd = dsu(st.size() + 10);
int cnt = 1;
for(auto x : st)
mp[x] = cnt++;
for(auto x : joins)
bool ok = dd.unite(mp[x.first], mp[x.second]);
cout << ans[dd.get(mp[x]) == dd.get(mp[y])] << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
int t;
cin >> t;
while(t--)
solve();
}
