DFS与BFS

图论：
一、图中DFS与BFS
数和图的存储方式：
m与n^2一个级别属于稠密图，m与n一个级别则属于稀疏图，可以从题目中明显看出来
稠密图：邻接矩阵
稀疏图：邻接表

#include<bits/stdc++.h>
using namespace std;
const int N = 100100;
int m,n;
int h[N],e[N],ne[N],idx;
int q[N],d[N];
bool st[N],stt[N];
int dis[N];

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void bfs(){             //默认源点是1，如果是其他点，就让stt[u]=true;q[++tt]=u;
    memset(st,false,sizeof st);
    int hh=0,tt=-1;
    stt[1]=true;
    q[++tt]=1;
    while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(!stt[j]){
                q[++tt]=j;
                stt[j]=true;
            }
        }
    }
}

int dfs(int u){
    st[u]=true;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j]){
            dfs(j);
            st[j]=true;
        }
    }
}

//栈模拟的DFS
// int sa[N];
// void dfs(int u){
//     int tt=-1;
//     sa[++tt]=u;
//     st[u]=true;
//     while(tt!=-1){
//         int t=sa[tt--];
//         for(int i=h[t];i!=-1;i=ne[i]){
//             int j=e[i];
//             if(!st[j]){
//                 sa[++tt]=j;
//                 st[j]=true;
//             }
//         }
//     }
// }

bool topsort(){
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++){
        if(!d[i]){
            q[++tt]=i;
        }
    }
    while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            d[j]--;
            if(!d[j]){
                q[++tt]=j;
            }
        }
    }
    return tt==n-1;
}

int main(){
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    return 0;
}