图算法中的常用代码
并查集模板
主要用于解决关于连通的一些问题
void Initial(){
for(int i=0;i<MAXN;i++){
father[i]=i;//根结点指向自己
height[i]=0;
//inDegree[i]=0;
//visit[i]=false;
}
}
int Find(int x){
if(father[x]!=x) father[x]=Find(father[x]);//注意写法，路径压缩
return father[x];
}
void Union(int x,int y){
x=Find(x);
y=Find(y);
if(x!=y){
if(height[x]height[y]) father[y]=x;//前面两种情况树高并没有变
else{
father[y]=x;
height[x]++;
}
}
return ;
}
邻接表
struct Edge{
int to;
int length;
Edge(int t,int l):to{t},length(l){}
};
vector graph[MAXN];
最小生成树
int Kruskal(int n,int edgeNumber){
Initial(n);
sort(edge,edge+edgeNumber);
int sum=0;
for(int i=0;i<edgeNumber;i++){
Edge current=edge[i];
//cout<<current.from<"<<current.to<<" "<<current.length<<endl;
if(Find(current.from)!=Find(current.to)){
Union(current.from,current.to);
sum+=current.length;
}
}
return sum;
}
最短路径
struct Point{//结点
int number;
int distance;
Point(int n,int d):number(n),distance(d){}
bool operatorp.distance;
}
};
int dis[MAXN];
void Dijkstra(int s){
priority_queue pqueue;
dis[s]=0;
pqueue.push(Point(s,dis[s]));
while(!pqueue.empty()){
int u=pqueue.top().number;//离源点最近的点
pqueue.pop();
for(int i=0;idis[u]+d){
dis[v]=dis[u]+d;
pqueue.push(Point(v,dis[v]));
}
}
}
return ;
}
拓扑排序
int inDegree[MAXN];
vector TopologicalSort(int n){
vector topology;
priority_queue<int,vector,greater > node;//逆向优先队列，为了实现拓扑序列不唯一时编号小的在前面
for(int i=1;i<=n;i++){//i是从1到n，即结点的编号
if(inDegree[i]==0){//先把初始入度为零的全部放入队列
node.push(i);
}
}
//求解拓扑序列时一定先把上一层的所有全部入队后再入队下一层，所以优先队列不会干扰
while(!node.empty()){
int u=node.top();
node.pop();
topology.push_back(u);
for(int i=0;i<graph[u].size();i++){//遍历当前pop出的结点的所有出弧
int v=graph[u][i];
inDegree[v]--;
if(inDegree[v]==0){//u的所有出弧全部去掉后如果有入度为零的则push进队列
node.push(v);
}
}
}
return topology;
}
关键路径
基于拓扑顺序去遍历的
void CriticalPath(int n){
vector topology;//拓扑序列
queue node;
for(int i=0;i<n;i++){
if(inDegree[i]==0){
node.push(i);
earliest[i]=1;//初始化为1,题目中的要求：1ns
}
}
while(!node.empty()){
int u=node.front();
topology.push_back(u);
node.pop();
for(int i=0;i=0;i--){
int u=topology[i];
if(graph[u].size()==0) latest[u]=earliest[u];//汇点的最晚开始时间初始化
else latest[u]=INF;//非汇点的最晚开始时间的初始化
for(int j=0;j<graph[u].size();j++){
int v=graph[u][j].to;
int l=graph[u][j].length;
latest[u]=min(latest[u],latest[v]-l);//逆向找最小，形成latest
}
}
}
作者：淅淅沥沥的熙
