来吧！最短路

邻接矩阵版

dij（）
{
初始化 1.dist，st数组 2.起点dist=0

while(顶点数--)
{
    t初始化-1
    t先=第一个没被访问的，再比较距离；

    从n个顶点选出距离最小的t后，标记t被访问。

    用t更新所有顶点(更新距离，前面的点)
}

}

int n,m,S,T;
int g1[N][N],g2[N][N];
int dist1[N],dist2[N],pre[N];
bool st[N];


int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < n - 1; i ++ )
    {

        int t = -1; 
        for (int j = 1; j <= n; j ++ )   
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        for (int j = 1; j <= n; j ++ )  
            dist[j] = min(dist[j], dist[t] + g[t][j]);
t每次i循环里不一样，总共复杂度m次，遍历了所有边

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

邻接表+priority_queue[HTML_REMOVED], greater[HTML_REMOVED]> heap;

判断无向连通 dfs

int dfs(int u)
{
    st[u]=true;
    int res=1;
    for(int i=1;i<=n;i++)
    {
        if(!st[i]&&g[u][i]) res=dfs(i)+res; 
    }
    return res;
}
int cnt=dfs(1); if(n==cnt)

判断集合中任意两点相连

every two distinct vertices in the clique are adjacent
（1,2） （1,3） （1,4） （2,3）（2,4）

bool check_clique(int cnt)
{
    bool success=true;
    for(int i=0;i<cnt;i++)
    {
        for(int j=i+1;j<cnt;j++)
            if(!g[vers[i]][vers[j]]) success=false;
    }
    return success;
}

是否前后相连 path

for(i=0;i<n;i++)
                {
                    if(g[v[i]][v[i+1]]==0)
                    {
                        puts("NO"); break;
                     } 
                }

连通块（带边的，走地图的bfs ）

1. 有几个连通块=顶点数-合并次数
2. 判断连通需添加边的个数:连通块个数-1

3. 删除一点——删除对应的边(包含该点的边不操作struct存边)

4. 2.
   ``` int cnt=n;
   for(int i=0;i<m;i++)
   {
   int a=e[i].a,b=e[i].b;
   int pa = find(a),pb=find(b);
   if(pa!=pb)
   {
   p[pa]=pb;
   cnt–;
   }
   }
   连通块数：cnt 需添加的边数：cnt-1

3. 

for(int i=0;i<m;i++)
{
int a=e[i].a,b=e[i].b;
if(a!=x&&b!=x)
{

        }

## 并查集
1. 初始化 p[i]=i;
2. 路径压缩,合并集合
3.求集合数，各集合人数:遍历所有人i，i的根所在的数组下标++；数组从大到小排序，＞0的都排在前面


2. 

int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
void unio(int a,int b)
{
a=find(a),b=find(b);
if(a!=b) p[a]=b;
}

3. 

for(int i=0;i[HTML_REMOVED]());
int s=0;
while(cnt[s]) s;
cout<<s<<endl;集合数
cout<<cnt[0];各集合人数
for(int i=1;i<s;i) cout<<” “<<cnt[i];
```