算法代码大全

shw4188 / 2023-05-14 / 原文

链式前向星

//初始化
int cnt,head[maxn];
struct Edge{
    int to,w,nxt;
}edge[maxn];
void init(){
    for(int i=0;i<=n;i++) head[i]=-1;
    cnt=0;
}
void add_edge(int u,int v,int w){
    edge[cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].nxt=head[u];
    head[u]=cnt++;
}
//遍历
for(int j=head[i];j!=-1;j=edge[j].nxt)

Dijkstra

struct Edge{
	int v,w,nxt; 
}e[maxn];
int head[maxn],cnt=0;
inline void addEdge(int u,int v,int w) {
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int n,m,s,dis[maxn];
struct node{
    int u,d;
    bool operator <(const node& rhs) const{
        return d>rhs.d;
    }
};
inline void Dijkstra() {
    for(register int i=1;i<=n;i++) dis[i]=2147483647;
    dis[s]=0;
    priority_queue<node> Q;
    Q.push((node){s,0});
    while(!Q.empty()){
        node fr=Q.top();
		Q.pop();
        int u=fr.u,d=fr.d;
        if(d!=dis[u]) continue;
        for(register int i=head[u];i;i=e[i].nxt){
            int v=e[i].v,w=e[i].w;
            if(dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                Q.push((node){v,dis[v]});
            }
        }
    }
}

Tarjan

vector<int>mp[maxn];
int ans[maxn],vis[maxn],dfn[maxn],low[maxn],color[maxn],s[maxn],n,m,tt,cnt,sig;
void Tarjan(int u){
    vis[u]=1;
    low[u]=dfn[u]=cnt++;
    s[++tt]=u;
    for(int i=0;i<mp[u].size();i++){
        int v=mp[u][i];
        if(vis[v]==0) Tarjan(v);
        if(vis[v]==1) low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u]){
        sig++;
        do{
            low[s[tt]]=sig;
            color[s[tt]]=sig;
            vis[s[tt]]=-1;
        }while(stack[tt--]!=u);
    }
}