圖的基本存儲的基本方式二

2019-11-08 01:55:29

字體：大中小

來源：轉載

供稿：網友

圖的基本存儲的基本方式二 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic 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

#include <stdio.h>#include <stdlib.h>typedef struct node{ int data; struct node *next;}node;int main(){ int n,m,u,v; int i; int a,b,q; node *head[500000],*p,*tail,*temp; while(~scanf("%d %d",&n,&m)){ for(i=0; i<n; i++)//初始化節點，一開始圖的每個節點都設為空 head[i] = NULL; while(m--){ scanf("%d %d",&u,&v); if(head[u]==NULL){//當個圖的節點為空的時，給他分配內存，在把這個節點到另一個有向邊的位置存到這個節點的數據域 head[u] = (node *)malloc(sizeof(struct node)); head[u]->data = v; head[u]->next = NULL;//下一個為空，千萬別忘記 } else{ temp = head[u]->next;//如果這個節點已經有了邊的話，那就逆序建立鏈表 p = (node *)malloc(sizeof(struct node)); p->data = v; p->next = temp; head[u]->next = p;// tail = head[u];// p = (node *)malloc(sizeof(struct node));//不知道為什么順序建就不行，哪位老鐵能給我解釋解釋// p->data = v;// p->next = NULL;// tail->next = p;// tail = p; } } scanf("%d",&q); while(q--){ int f = 0; scanf("%d %d",&a,&b); if(head[a]==NULL) printf("No/n"); else{ temp = head[a]; while(temp){ if(temp->data==b){ f = 1; break; } temp = temp->next; } if(f)//這里要注意的是if判斷放在大else里面，要不然如果是No的話，會輸出兩個的 printf("Yes/n"); else printf("No/n"); } } } return 0;}

上一篇：final修飾符

下一篇：springmvc限流攔截器