链式前向星
//初始化
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);
}
}