邻接表来存储图

ゞ浴缸里的玫瑰 2022-05-17 09:34 152阅读 0赞

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。

Sample Input

2 1
    0 1
    2
    0 1
    1 0

Sample Output

Yes
    No

与邻接矩阵不同的是，用邻接链表来处理图会更节省空间，但是也更复杂一点相比较邻接矩阵这种数组而言。**图的邻接链表实质上就是逆序建立链表的过程**，但要注意的时，建立完成后，要将连接表中的元素进行排序，这样广度优先遍历出来的数据才符合逻辑！

代码如下：

#include<bits/stdc++.h>
    using namespace std;
    typedef struct sdut
    {
        int a;
        sdut *next;
    }zxx;
    zxx *q[500005],*p;
    int flag;
    void creat(int u,int v)
    {
        if(!q[u])
        {
            q[u]=new sdut;
            q[u]->a=v;
            q[u]->next=NULL;
        }
        else
        {
            p=new sdut;
            p->a=v;
            p->next=q[u]->next;
            q[u]->next=p;
        }
    }
    int judge(int u,int v)
    {
        p=q[u];
        while(p)
        {
            if(p->a==v)
                return 1;
            else
                p=p->next;
        }
        return 0;
    }
    
    int main()
    {
        int n,m,u,v,f;
        while(cin>>n>>m)
        {
            for(int i=0;i<n;i++)
                q[i]=NULL;
            for(int i=0;i<m;i++)
            {
                cin>>u>>v;
                creat(u,v);
            }
            cin>>f;
            while(f--)
            {
    
                cin>>u>>v;
                if(judge(u,v))
                    cout<<"Yes"<<endl;
                else
                    cout<<"No"<<endl;
            }
        }
    }