- 797. 所有可能的路径">13.1 797. 所有可能的路径
- 207. 课程表">13.2 207. 课程表
- 210. 课程表 II">13.3 210. 课程表 II
- 785. 判断二分图">13.4 785. 判断二分图
- 886. 可能的二分法">13.5 886. 可能的二分法
- 990. 等式方程的可满足性">13.6 990. 等式方程的可满足性
- 1584. 连接所有点的最小费用">13.7 1584. 连接所有点的最小费用
- 743. 网络延迟时间">13.8 743. 网络延迟时间
- 1631. 最小体力消耗路径">13.9 1631. 最小体力消耗路径
- 1514. 概率最大的路径">1514. 1514. 概率最大的路径
13.1 797. 所有可能的路径
class Solution {public:vector<vector<int>> result;vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {vector<int> path;traverse(graph,0,path);return result;}void traverse(vector<vector<int>>& graph,int s,vector<int>& path){path.push_back(s);int n=graph.size();if(s==n-1){result.push_back(path);path.pop_back();return;}for(int g:graph[s]){traverse(graph,g,path);}path.pop_back();}};
13.2 207. 课程表
class Solution {public:vector<bool> onPath;vector<bool> visited;bool hasCycle=false;bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {//建图vector<vector<int>> graph(numCourses);for(auto p:prerequisites){int from=p[1],to=p[0];graph[from].push_back(to);}onPath.resize(numCourses);visited.resize(numCourses);for(int i=0;i<numCourses;i++){traverse(graph,i);}return !hasCycle;}//看路径中是否有相同的节点，有则循环。void traverse(vector<vector<int>>& graph,int s){if(onPath[s]){hasCycle=true;}if(visited[s]||hasCycle){return;}visited[s]=true;onPath[s]=true;for(int p:graph[s]){traverse(graph,p);}onPath[s]=false;}};
13.3 210. 课程表 II
class Solution {public:vector<bool> visited;vector<bool> onPath;vector<int> result; //记录后序遍历结果bool hasCycle=false;vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> graph(numCourses);for(auto p:prerequisites){int from=p[1],to=p[0];graph[from].push_back(to);}visited.resize(numCourses);onPath.resize(numCourses);for(int i=0;i<numCourses;i++){traverse(graph,i);}if(hasCycle){return {};}//逆后序reverse(result.begin(),result.end());return result;}void traverse(vector<vector<int>>& graph,int s){if(onPath[s]){hasCycle=true;}if(visited[s]||hasCycle){return;}onPath[s]=true;visited[s]=true;for(int i:graph[s]){traverse(graph,i);}result.push_back(s);onPath[s]=false;}};
13.4 785. 判断二分图
//DFS
class Solution {
public:
bool result=true;
vector<int> visited,color;//记录是否访问过、节点颜色
bool isBipartite(vector<vector<int>>& graph) {
int n=graph.size();
visited.resize(n);
color.resize(n);
for(int i=0;i<n;i++){
traverse(graph,i);
}
return result;
}
void traverse(vector<vector<int>>& graph,int v){
if(!result) return;
if(visited[v]){
return;
}
visited[v]=true;
for(int g:graph[v]){
if(!visited[g]){
//染上不同颜色
color[g]=!color[v];
traverse(graph,g);
}else{
if(color[g]==color[v]){
result=false;
}
}
}
}
};
//BFS
class Solution {
public:
bool result=true;
vector<int> visited,color;//记录是否访问过、节点颜色
bool isBipartite(vector<vector<int>>& graph) {
int n=graph.size();
visited.resize(n);
color.resize(n);
for(int i=0;i<n;i++){
bfs(graph,i);
}
return result;
}
void bfs(vector<vector<int>>& graph,int start){
if(visited[start]){
return;
}
visited[start]=true;
queue<int> q;
q.push(start);
while(!q.empty()&&result){
int v=q.front();
q.pop();
for(int w:graph[v]){
if(!visited[w]){
color[w]=!color[v];
visited[w]=true;
q.push(w);
}else{
if(color[w]==color[v]){
result=false;
}
}
}
}
}
};
13.5 886. 可能的二分法
class Solution {
public:
bool result=true;
vector<int> color,visited;
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
//建立图
vector<vector<int>> graph(n+1);
for(vector<int> dis:dislikes){
int from=dis[1],to=dis[to];
//双向图
graph[from].push_back(to);
graph[to].push_back(from);
}
color.resize(n+1);
visited.resize(n+1);
for(int i=1;i<=n;i++){
traverse(graph,i);
}
return result;
}
void traverse(vector<vector<int>>& graph,int v){
if(!result) return;
if(visited[v]) return;
visited[v]=true;
for(int w:graph[v]){
if(!visited[w]){
color[w]=!color[v];
traverse(graph,w);
}else{
if(color[w]==color[v]){
result=false;
}
}
}
}
};
13.6 990. 等式方程的可满足性
//并查集
class Solution {
public:
class UF{
public:
int count;
vector<int> parent;
vector<int> size;
UF(int n){
count=n;
for(int i=0;i<n;i++){
parent.push_back(i);
size.push_back(1);
}
}
void myUnion(int p,int q){
int rootP=find(p);
int rootQ=find(q);
if(rootP==rootQ){
return;
}
//小树接到大树下
if(size[rootP]>size[rootQ]){
parent[rootQ]=rootP;
size[rootP]+=size[rootQ];
}else{
parent[rootP]=rootQ;
size[rootQ]+=size[rootP];
}
count--;
}
//判断p q是否连通
bool connected(int p,int q){
return find(p)==find(q);
}
//返回根节点
int find(int x){
while(parent[x]!=x){
//路径压缩
parent[x]=parent[parent[x]];
x=parent[x];
}
return x;
}
int myCount(){
return count;
}
};
bool equationsPossible(vector<string>& equations) {
UF uf(26);
for(const string& eq:equations){
if(eq[1]=='='){
int x=eq[0]-'a';
int y=eq[3]-'a';
//联通a==b中的a和b
uf.myUnion(x,y);
}
}
for(const string& eq:equations){
if(eq[1]=='!'){
int x=eq[0]-'a';
int y=eq[3]-'a';
//判断a!=b中的a和b是否和 a==b中的交叉
if(uf.connected(x,y)){
return false;
}
}
}
return true;
}
};
13.7 261.已图判树
class Solution{
public:
class UF{
vector<int> parent,size;
int count;
UF(int n){
count=n;
for(int i=0;i<n;i++){
parent.push_back(i);
size.push_back(1);
}
}
void myUnion(int p,int q){
int rootP=find(p);
int rootQ=find(Q);
if(rootP==rootQ){return;}
if(size[rootP]>size[rootQ]){
parent[rootQ]=rootP;
size[rootP]+=size[rootQ];
}else{
parent[rooP]=rootQ;
size[rootQ]+=size[rootP];
}
count--;
}
int find(int x){
while(x!=parent[x]){
parent[x]=parent[parent[x]];
x=parent[x];
}
return x;
}
bool connected(int p,int q){
return find(p)==find(q);
}
int myCount(){
return count;
}
};
bool validTree(int n,vector<vector<int>>& edges){
UF uf(n);
for(vector<int> ed:edges){
int u=ed[0],v=ed[1];
//如果已经在同一个连通分量中，那么就会产生环
if(uf.connected(u,v)){
return false;
}
//不会产生环，可以是树的一部分。
uf.myUnion(u,v);
}
//保证最后只形成一个树，即只有一个连通分量
return uf.count()==1;
}
};
13.7 1584. 连接所有点的最小费用
//Kruskal
class Solution {
public:
class Edge{
public:
int p1,p2,dist;
Edge(int _p1,int _p2,int _dist){
p1=_p1;p2=_p2;dist=_dist;
}
};
class myCompare{
public:
bool operator()(Edge x,Edge y){
return x.dist<y.dist;
}
};
class UF{
public:
int count;
vector<int> parent,size;
UF(int n){
count=n;
for(int i=0;i<n;i++){
parent.push_back(i);
size.push_back(1);
}
}
void myUnion(int p,int q){
int rootP=find(p);
int rootQ=find(q);
if(rootP==rootQ){
return;
}
if(size[rootP]>size[rootQ]){
parent[rootQ]=rootP;
size[rootP]+=size[rootQ];
}else{
parent[rootP]=rootQ;
size[rootQ]+=size[rootP];
}
count--;
}
int find(int x){
while(x!=parent[x]){
parent[x]=parent[parent[x]];
x=parent[x];
}
return x;
}
bool connected(int p,int q){
return find(p)==find(q);
}
int myCount(){
return count;
}
};
int minCostConnectPoints(vector<vector<int>>& points) {
int n=points.size();
vector<Edge> graph;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
int xi=points[i][0],yi=points[i][1];
int xj=points[j][0],yj=points[j][1];
int dist=abs(xi-xj)+abs(yi-yj);
graph.push_back(Edge(i,j,dist));
}
}
//按照权重排序
sort(graph.begin(),graph.end(),myCompare());
int mst=0;
UF uf(n);
for(auto ed:graph){
int u=ed.p1,v=ed.p2,w=ed.dist;
//如果会产生环，不能加入mst
if(uf.connected(u,v)){
continue;
}
//不会产生环，加入mst
mst+=w;
uf.myUnion(u,v);
}
return mst;
}
};
//Prim
class Solution {
public:
class Edge{
public:
int p1,p2,dist;
Edge(int _p1,int _p2,int _dist){
p1=_p1;p2=_p2;dist=_dist;
}
};
class myCompare{
public:
bool operator()(Edge& x,Edge& y){
return x.dist>y.dist;
}
};
int minCostConnectPoints(vector<vector<int>>& points) {
int n=points.size();
visited.resize(n);
//创建图，每个顶点存储其相邻边即可
vector<vector<pair<int,int>>> graph(n);
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
int xi=points[i][0],yi=points[i][1];
int xj=points[j][0],yj=points[j][1];
int dist=abs(xi-xj)+abs(yi-yj);
//双向图
graph[i].push_back({j,dist});
graph[j].push_back({i,dist});
}
}
int mst=0;
//以0为起点开始
visited[0]=true;
cut(graph,0);
while(!pq.empty()){
Edge edge=pq.top();
pq.pop();
int to=edge.p2;
int weight=edge.dist;
if(visited[to]) continue;
visited[to]=true;
mst+=weight;
cut(graph,to);
}
return mst;
}
private:
//优先级队列，小根堆
priority_queue<Edge,vector<Edge>,myCompare> pq;
//遍历数组
vector<bool> visited;
//以s为起点的横切边，依次加入队列
void cut(vector<vector<pair<int,int>>>& graph,int s){
for(auto& g:graph[s]){
int to=g.first;
int weight=g.second;
if(visited[to]) continue;
pq.push(Edge(s,to,weight));
}
}
};
13.8 743. 网络延迟时间
class Solution {
public:
class State{
public:
int id;
int dist; //从start到该点的距离
State(int _id,int _dist){
id=_id;dist=_dist;
}
};
class myCompare{
public:
bool operator()(State s1,State s2){
return s1.dist>s2.dist;
}
};
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
//建立图
vector<vector<State>> graph(n+1);
for(auto& edge:times){
int from=edge[0],to=edge[1],weight=edge[2];
graph[from].push_back(State(to,weight));
}
//计算从起点开始的最短路径
vector<int> distTo(graph.size(),INT_MAX);
distTo=dijkstra(graph,k);
int res=0;
for(int i=1;i<distTo.size();i++){
if(distTo[i]==INT_MAX){
return -1;
}
res=max(res,distTo[i]);
}
return res;
}
//从start开始到其他节点的最短路径
vector<int> dijkstra(vector<vector<State>>& graph,int start){
vector<int> distTo(graph.size(),INT_MAX);
distTo[start]=0;
priority_queue<State,vector<State>,myCompare> pq;
pq.push(State(start,0));
while(!pq.empty()){
State curState=pq.top();
pq.pop();
int curID=curState.id;
int curDist=curState.dist;
if(curDist>distTo[curID]){
continue;
}
for(auto& g:graph[curID]){
int nextID=g.id;
int nextDist=distTo[curID]+g.dist;
if(distTo[nextID]>nextDist){
distTo[nextID]=nextDist;
pq.push(State(nextID,nextDist));
}
}
}
return distTo;
}
};
13.9 1631. 最小体力消耗路径
class Solution {
public:
vector<vector<int>> dirs={{0,1},{0,-1},{1,0},{-1,0}};
class State{
public:
int x,y,effort;
State(int _x,int _y,int _effect){
x=_x;y=_y;effort=_effect;
}
};
class myCompare{
public:
bool operator()(State x,State y){
return x.effort>y.effort;
}
};
//返回一个点的相邻点，数组形式
vector<vector<int>> adj(vector<vector<int>>& matrix,int x,int y){
int m=matrix.size(),n=matrix[0].size();
vector<vector<int>> neighbor;
for(auto& dir:dirs){
int nx=x+dir[0];
int ny=y+dir[1];
if(nx<0||nx>=m||ny<0||ny>=n){
continue;
}
neighbor.push_back({nx,ny});
}
return neighbor;
}
int minimumEffortPath(vector<vector<int>>& heights) {
int m=heights.size(),n=heights[0].size();
vector<vector<int>> effortTo(m,vector<int>(n,INT_MAX));
//起点开始
effortTo[0][0]=0;
//小根堆
priority_queue<State,vector<State>,myCompare> pq;
pq.push(State(0,0,0));
while(!pq.empty()){
State curState=pq.top();
pq.pop();
int curX=curState.x;
int curY=curState.y;
int curEffort=curState.effort;
//到达终点，提前结束
if(curX==m-1&&curY==n-1){
return curEffort;
}
if(curEffort>effortTo[curX][curY]){
continue;
}
//遍历邻居，找最小消耗
for(auto nei:adj(heights,curX,curY)){
int nextX=nei[0];
int nextY=nei[1];
//一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
int nextEffort=max(effortTo[curX][curY],abs(heights[curX][curY]-heights[nextX][nextY]));
//更新dp table
if(nextEffort<effortTo[nextX][nextY]){
effortTo[nextX][nextY]=nextEffort;
pq.push(State(nextX,nextY,nextEffort));
}
}
}
return -1;
}
};
1514. 1514. 概率最大的路径
class Solution {
public:
class State{
public:
int id;
double prob;
State(int _id,double _prob){
id=_id;
prob=_prob;
}
};
class myCompare{
public:
bool operator()(State& x,State& y){
return x.prob<y.prob;
}
};
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
//创建图
vector<vector<pair<int,double>>> graph(n);
for(int i=0;i<edges.size();i++){
int from=edges[i][0],to=edges[i][1];
double prob=succProb[i];
graph[from].push_back({to,prob});
graph[to].push_back({from,prob});
}
vector<double> probTo(n,0);
probTo[start]=1;
//小根堆
priority_queue<State,vector<State>,myCompare> pq;
pq.push(State(start,1));
while(!pq.empty()){
State curState=pq.top();
pq.pop();
int curId=curState.id;
double curProb=curState.prob;
//遇到终点提前返回
if(curId==end){
return curProb;
}
if(curProb<probTo[curId]){
continue;
}
for(auto& nei:graph[curId]){
int nextId=nei.first;
double nextProb=nei.second*probTo[curId];
if(probTo[nextId]<nextProb){
probTo[nextId]=nextProb;
pq.push(State(nextId,nextProb));
}
}
}
return 0.0;
}
};
若有收获，就点个赞吧
0 人点赞
