Problem Description
解决图论问题,首先就要思考用什么样的方式存储图。但是小鑫却怎么也弄不明白如何存图才能有利于解决问题。你能帮他解决这个问题么?
Input
多组输入,到文件结尾。
每一组第一行有两个数n、m表示n个点,m条有向边。接下来有m行,每行两个数u、v代表u到v有一条有向边。第m+2行有一个数q代表询问次数,接下来q行每行有一个询问,输入两个数为a,b。
注意:点的编号为0~n-1,2<=n<=500000 ,0<=m<=500000,0<=q<=500000,a!=b,输入保证没有自环和重边
Output
对于每一条询问,输出一行。若
a
到
b
可以直接连通输出
Yes
,否则输出
No
。
Example Input
2 1
0 1
2
0 1
1 0
Example Output
Yes
No
Hint
Author
lin
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 5;
typedef struct node {
int data;
struct node *next;
} node;
node *a[maxn];
int main() {
ll n, m;
while(~scanf("%lld%lld", &n, &m)) {
for(int i = 0; i < n; i++) {
a[i] = NULL;
}
while(m--) {
int u, v;
scanf("%d%d", &u, &v);
if(!a[u]) {
a[u] = new node;
a[u]->data = v;
a[u]->next = NULL;
} else {
node *p, *q;
p = new node;
p->data = v;
p->next = NULL;
q = a[u]->next;
p->next = q;
a[u]->next = p;
}
}
ll q;
scanf("%lld", &q);
while(q--) {
int flag = 0;
int u, v;
scanf("%d%d", &u, &v);
if(!a[u]) {
printf("No\n");
} else {
node *p = a[u];
while(p) {
if(p->data == v) {
flag = 1;
break;
}
p = p->next;
}
if(flag) {
printf("Yes\n");
} else {
printf("No\n");
}
}
}
}
return 0;
}
/***************************************************
User name:
Result: Accepted
Take time: 52ms
Take Memory: 4000KB
Submit time: 2018-01-28 19:22:59
****************************************************/