解決圖論問(wèn)題，首先就要思考用什么樣的方式存儲(chǔ)圖。但是小鑫卻怎么也弄不明白如何存圖才能有利于解決問(wèn)題。你能幫他解決這個(gè)問(wèn)題么？ Input 多組輸入，到文件結(jié)尾。
每一組第一行有兩個(gè)數(shù)n、m表示n個(gè)點(diǎn)，m條有向邊。接下來(lái)有m行，每行兩個(gè)數(shù)u、v代表u到v有一條有向邊。第m+2行有一個(gè)數(shù)q代表詢問(wèn)次數(shù)，接下來(lái)q行每行有一個(gè)詢問(wèn)，輸入兩個(gè)數(shù)為a，b。
注意：點(diǎn)的編號(hào)為0~n-1，2<=n<=500000 ，0<=m<=500000，0<=q<=500000，a!=b，輸入保證沒(méi)有自環(huán)和重邊 Output 對(duì)于每一條詢問(wèn)，輸出一行。若a到b可以直接連通輸出Yes，否則輸出No。 Example Input
2 1 0 1 2 0 1 1 0
Example Output
Yes No
鄰接表存儲(chǔ)
#include <cstdio>#include <iostream>using namespace std;struct node{ int data; struct node *next;}*p,*q,*head[500001];int main(){ int m,n,u,v,a,b,t,c,d; while(cin>>n>>m) { int i; for(i=0;i<n;i++) { head[i]=NULL; } while(m--) { cin>>u>>v; if(head[u]==NULL) { head[u]=new node; head[u]->data=v; head[u]->next=NULL; } else { q=head[u]->next; p=new node; p->data=v; p->next=q; head[u]->next=p; } } cin>>t; while(t--) { int flag=0; cin>>c>>d; if(head[c]==NULL) { printf("No/n"); } else { q=head[c]; while(q) { if(q->data==d) { flag=1; break; } q=q->next; } if(flag) printf("Yes/n"); else printf("No/n"); } } } return 0;}/***************************************************User name:Result: AcceptedTake time: 120msTake Memory: 3952KBSubmit time: 2017-02-16 20:38:26****************************************************/新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
