图的基本存储的基本方式二

xiaoxiao2021-02-28  9

Problem Description

解决图论问题,首先就要思考用什么样的方式存储图。但是小鑫却怎么也弄不明白如何存图才能有利于解决问题。你能帮他解决这个问题么?

Input

  多组输入,到文件结尾。

每一组第一行有两个数nm表示n个点,m条有向边。接下来有m行,每行两个数uv代表uv有一条有向边。第m+2行有一个数q代表询问次数,接下来q行每行有一个询问,输入两个数为ab

注意:点的编号为0~n-12<=n<=500000 0<=m<=5000000<=q<=500000a!=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 ****************************************************/
转载请注明原文地址: https://www.6miu.com/read-1650184.html

最新回复(0)