前言：    圖論乃noip之重要知識點，但有點難理解 本人因此吃過不少虧

     因為本人實在太弱，所以此篇乃正宗<蒟蒻專屬文章>

正文：（本文僅介紹圖論中的重點、難點，其餘部分略將或不講）

       圖一般來說有二種存儲方法：鄰接矩陣和鄰接表

鄰接矩陣：

      存儲：拿二維數組來存
　　

for(int i=1;i<=n;++i){   //f[q][z]表示點q與點z有沒有邊相連接
    cin>>q>>z;  //noip基本別指望，最多三四十分
    f[q][z]=1;  //無向邊要存雙向 
    f[z][q]=1;
} 

       可是，雖然存儲簡單，可效率也太低了（尤其是些超級稀疏的矩陣）

　　而且，壞處還沒完：讀取效率也很低！

       讀取：

cin>>x;//讀入x，查與x有關的點 
for(int i=1;i<=n;++i){  //據說++i比i++快一些 
    if(f[x][i]==1){
        cout<<i<<" ";
    } 
} 

 這麼暴力的for迴圈，不超時才怪呢

  所以，另一種辦法來了：鄰接表！！

 原理：

     通過鏈表的形式，高效的存儲/讀取邊

先使用struct：（我太蒻，只會用struct存）

struct node{
           int u,v,next;//u起點，v終點，next待會在說 啥意思 
   }e[MAXN*2]; //無向圖要*2（原因：要存兩次）！！！！有向圖似乎只要一倍 
   //這類數組名都用e，養成好習慣 

讀取：

for(int i=1;i<=n;++i){
       cin>>q>>z;  //這類函數名名都用e，養成好習慣 
       add(q,z);  //無向邊要存雙向 
       add(z,q);  //通常 用自定義函數實現 
   }

add（加邊函數）：    註意：要定義head數組，表示點i當前的第一個連接的數組下標！！！！！

代碼：

void add(int x,int y,){
   ++tot;
   e[tot].u=x;
   e[tot].v=y;
   e[tot].next=head[x]; 
   head[x]=tot;
}

一些question&Answer&註意事項:

1:為什麼偏偏要插隊？

Answer：因為如果不插隊，將要加的邊就沒法指向上一個了（難道你還for一遍？）；

2：鏈表結構其實還有很多其餘的辦法實現，但我寫的這種更適合初學者

（emm.....好像就兩個也）

 “遍歷”方式：

cin>>a; //問和a號點相鄰的邊有哪些
    for(int i=head[a];i!=0;i=e[i].next){  //從點a的第一條邊開始，若為0結束 
        cout<<e[i].u<<" "<<e[i].v<<endl;   // 到下一個數組下標 
    } 

（完）

寫在後面的話：

     這是我的第一篇博客（bug一定很多）

　　本人的個人主頁（洛谷）https://www.luogu.com.cn/user/236929  

    本人的個人主頁https://www.cnblogs.com/Craker/

歡迎來訪！

謝謝！

本人QQ：2783119105

本人郵箱：[email protected]

如有問題，請在評論區指出或私信我，

謝謝！