Pagini recente » Cod sursa (job #1867689) | Cod sursa (job #2828819) | Cod sursa (job #2350633) | Cod sursa (job #1628739) | Cod sursa (job #542374)
Cod sursa(job #542374)
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
#define MAXN 100005
int depend[MAXN];
int n, m, q;
bool contor[MAXN];
int conex = 1;
deque <int> deq[MAXN];
vector <int> lista[MAXN];
int tata[MAXN];
vector <int> goss[MAXN];
ifstream f("gossips.in");
ofstream g("gossips.out");
void vecini (int nod)
{
contor[nod] = 1;
deq[conex].push_back(nod);
depend[nod] = conex;
for (unsigned int i = 0; i < lista[nod].size(); ++i)
if ( ! contor[lista[nod][i]] )
vecini(lista[nod][i]);
}
int get_father (int nod, int y)
{
if (! tata[nod])
return 0;
goss[tata[nod]].push_back(y);
get_father (tata[nod], y);
return 0 ;
}
void get_son (int nod, int y)
{
goss[nod].push_back(y);
for (unsigned int i = 0; i < lista[nod].size(); ++i)
if (lista[nod][i] != tata[nod])
get_son (lista[nod][i], y);
}
int search (int x, int nod)
{
for (unsigned int i = 0; i < goss[x].size(); ++i)
if (goss[x][i] == nod)
return 1;
return 0;
}
int main()
{
f >> n >> m >> q;
for (int i = 1; i <= m; ++i)
{
int a, b;
f >> a >> b;
lista[a].push_back(b);
lista[b].push_back(a);
tata[b] = a;
}
for (int i = 1; i <= n; ++i)
{
if (contor[i])
continue;
contor[i] = 1;
deq[conex].push_back(i);
depend[i] = conex;
for (unsigned int j = 0; j < lista[i].size(); ++j)
if ( ! contor[lista[i][j]] )
vecini(lista[i][j]);
++conex;
}
for (int i = 1; i <= q; ++i)
{
int type, x, y;
f >> type >> x >> y;
if(depend[x] == depend[y])
{
g << "YES\n";
continue;
}
if (type == 2)
{
while (y != 0)
{
goss[x].push_back(y);
get_father(x, y);
for (unsigned int j = 0; j < lista[x].size(); ++j)
if (lista[x][j] != tata[x])
get_son(lista[x][j], y);
y = tata[y];
}
}
if (type == 1)
{
if (search(x, y))
g << "YES\n";
else
g <<"NO\n";
}
}
return 0;
}