Pagini recente » Cod sursa (job #582621) | Cod sursa (job #1859863) | Cod sursa (job #2717107) | Cod sursa (job #2975688) | Cod sursa (job #1550465)
#include <fstream>
#include <iostream>
#include <vector>
#include <tuple>
#include <set>
using namespace std;
void dfs(const int cur, const vector<vector<int>>& copii, vector<tuple<int, int>>& st_fin, int& p){
get<0>(st_fin[cur]) = p++;
for(const auto next : copii[cur]){
dfs(next, copii, st_fin, p); }
get<1>(st_fin[cur]) = p++; }
int main(){
ifstream f("gossips.in");
ofstream g("gossips.out");
int n, m, q;
f >> n >> m >> q;
vector<int> tata(n+1, 0);
vector<vector<int>> copii(n+1);
for(int i = 0, a, b; i < m; ++i){
f >> a >> b;
tata[b] = a; }
for(int i = 1; i <= n; ++i){
copii[tata[i]].push_back(i); }
vector<int> nume(n+1, 0);
for(int i = 1; i <= n; ++i){
if(tata[i] != 0){
continue; }
vector<int> st = {i};
nume[i] = i;
while(!st.empty()){
const int cur = st.back();
st.pop_back();
for(const auto next : copii[cur]){
nume[next] = nume[cur];
st.push_back(next); } } }
vector<tuple<int, int>> st_fin(n+1);
{
int p = 0;
dfs(0, copii, st_fin, p); }
vector<set<tuple<int, int>>> ce_stie_nume(n+1);
for(int i = 0, s, x, y; i < q; ++i){
f >> s >> x >> y;
if(s == 1){
auto it = ce_stie_nume[nume[x]].lower_bound(st_fin[y]);
if(it != end(ce_stie_nume[nume[x]]) && get<1>(*it) <= get<1>(st_fin[y])){
g << "YES\n"; }
else{
g << "NO\n"; } }
else{
ce_stie_nume[nume[x]].insert(st_fin[y]); } }
return 0; }