\(dijkstra\)单源最短路径:

void dijkstra(int s){    memset(dis,100,sizeof(dis));    memset(vis,0,sizeof(vis));    priority_queue< pair
    
      > q;    dis[s]=0; q.push(make_pair(0,s));    while(!q.empty())    {        int u=q.top().second; q.pop();        if(vis[u]) continue;        vis[u]=1;        for(int i=head[u];i;i=edge[i].next)        {            int v=edge[i].to;            if(dis[v]>dis[u]+edge[i].dis)            {                dis[v]=dis[u]+edge[i].dis;                if(!vis[v]) q.push(make_pair(-dis[v],v));            }        }    }}
    

\(spfa\)单源最短路径

void kruskal(){    for(int i=1;i<=n;++i) fa[i]=i;    sort(e+1,e+m+1,cmp);    int cnt=0;    for(int i=1;i<=m;++i)    {        int x=find(e[i].u),y=find(e[i].v);        if(x!=y)        {            fa[x]=y;            ans+=e[i].w;            if(++cnt==n-1) break;        }    }}

\(tarjan\)求强连通分量

void tarjan(int rt){    dfn[rt]=low[rt]=++c;    st[++top]=rt;    for(int i=head[rt];i;i=edge[i].next)    {        int v=edge[i].to;        if(!dfn[v])        {            tarjan(v);            low[rt]=min(low[rt],low[v]);        }        else if(!color[v]) low[rt]=min(low[rt],dfn[v]);    }    if(dfn[rt]==low[rt])    {        color[rt]=++col;        ++size[col];        while(st[top]!=rt)        {            color[st[top--]]=col;            ++size[col];        }        --top;    }}

强连通分量缩点

void rebuild(){    for(int i=1;i<=n;++i)    {        for(int j=head[i];j;j=edge[j].next)        {            int v=edge[j].to;            if(color[i]!=color[v])            {                son[color[i]].push_back(color[v]);                ++rd[color[v]];            }        }    }}

\(kruskal\)最小生成树

void kruskal(){    for(int i=1;i<=n;++i) fa[i]=i;    sort(e+1,e+m+1,cmp);    int cnt=0;    for(int i=1;i<=m;++i)    {        int x=find(e[i].u),y=find(e[i].v);        if(x!=y)        {            fa[x]=y;            ans+=e[i].w;            if(++cnt==n-1) break;        }    }}