图上问题(并查集&dfs)与单源最短路

图上问题(并查集&dfs)与单源最短路

Lionlnuc
Lionlnuc Lv4
  2026-01-27 2026-01-27 创建   2026-01-27 2026-01-27 更新      

回家胃疼了一周慢慢养病中……

先不急着做第一个题，先来回忆一下并查集的模板题。

并查集模板题

题目链接： https://www.luogu.com.cn/problem/P3367
思路：
字面意思，并查集一共有两种操作，合并和查询。
并查集是一种树形的数据结构，使用 fa[x]存节点 x 的父节点。在初始化时每个节点的父节点都是它自己。
如果要查找两个集合是否在同一个集合中，我们可以去找这两个的集合的根是否相同。根节点的父节点是自己。
带路径压缩的查找，可以在查找过程中将遇到的节点的父节点都替换为根节点。
合并操作，找到两个集合的根，将任意一个集合的根指向另一个集合的根。
启发式合并，把小集合的根指向大集合。（需要使用 size 记录树的大小）
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N=2e+5;
int f[N];
int s[N];//用来存储树的大小
int find(int x)//查询节点x的根
{
    if(f[x]==x)return x;
    else return f[x]=find(f[x]);//路径压缩
}
void merge(int x,int y)//这里采用启发式合并，默认把小树挂到大树y上。
{
    x=find(x),y=find(y);
    if(x==y)return;
    else{
        if(s[x]>s[y]) swap(x,y);
        f[x]=y;
        s[y]+=s[x];
    }
}
void solve()
{
    int n,m;
    cin>>n>>m;
    int z,x,y;
    for(int i=1;i<=n;i++)
    {
        f[i]=i;//初始化
    }
    for(int i=0;i<m;i++)
    {
        cin>>z>>x>>y;
        if(z==1){
            merge(x,y);
        }else{
            if(find(x)==find(y))cout<<"Y";
            else cout<<"N";
            cout<<endl;
        }
    }
}
signed main(){
	IOS
	//int t;
	//cin>>t;
	int t=1;
	while(t--)
	{
		solve();
	}
}

P2661 信息传递

题目链接： https://www.luogu.com.cn/problem/P2661
思路：
在看过上面的并查集之后这个题应该不算问题。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N=2e5+5;
int f[N];
int cnt=0,ans=0x3f3f3f;
int find(int x)//查询节点x的根
{
    ++cnt;
    if(f[x]==x)return x;
    else return find(f[x]);//路径压缩
}
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        f[i]=i;//初始化
    }
    for(int i=1;i<=n;i++)
    {
        int t;
        cin>>t;
        cnt=0;
        int root=find(t);
        if(root==i){
            ans=min(ans,cnt);
        }else f[i]=t;
    }
    cout<<ans;
}
signed main(){
	IOS
	//int t;
	//cin>>t;
	int t=1;
	while(t--)
	{
		solve();
	}
}

P3916 图的遍历

题目链接： https://www.luogu.com.cn/problem/P3916
题目大意： 给出 N 个点，M 条边的有向图，对于每个点 v ，求 A(v) 表示从点 v 出发，能到达的编号最大的点。
思路：
看到这种一个点能到好几个点，然后还要找一个编号最大的点，第一个想到的应该就是 dfs 了。这里我们可以反向思维一下，如果反向建立连边的话，从序号较大的节点 dfs 如果一个节点被访问过，那么访问的起始点就是最大值了。
这里介绍两种存图方式：
邻接表存储（链式前向星）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int h[N];  // 头指针数组，h[i]表示节点i的第一个邻接点在数组中的索引
int e[M];  // 边数组，存储边的终点节点
int ne[M]; // next数组，存储下一条邻接边的索引
int idx;   // 当前可用的空位置索引
void add(int a,int b)//a所对应的单链表中插入b a作为根
{ 
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++; 
}
初始时会将h置为-1表示无邻接点
idx初始值为0
执行add函数时，add(1,2)
e[0]=2,ne[0]=-1,h[1]=0;
此时的链表结构 [1] -> [2] -> NULL
for(int i=h[x];i!=-1;i=ne[i])遍历方法

vector 存图

1
2
3
4
vector<int> p[N];
p[b].push_back(a);
这个存图看起来更简单
for(int i=0;i<p[x].size();i++)遍历也是

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//邻接表存图
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N=1e5+5;
int h[N],e[N],ne[N],idx,ans[N];
void add(int a,int b)//a所对应的单链表中插入b  a作为根 
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
//h[x]邻接表存储树，有n个节点，所以需要n个队列头节点
//e[x]存储元素
//ne[x]存储列表的next值
void dfs(int x,int d)
{
    if(ans[x]) return;
    ans[x]=d;
    for(int i=h[x];i!=-1;i=ne[i]){
        int y=e[i];
        dfs(y,d);//递归标记所有邻接点
    }
}
void solve()
{
    memset(h,-1,sizeof h);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(b,a);
    }
    for(int i=n;i>0;i--)
    {
        if(!ans[i])dfs(i,i);
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}
signed main(){
	IOS
	//int t;
	//cin>>t;
	int t=1;
	while(t--)
	{
		solve();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//vector存图
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N=1e5+5;
vector<int> p[N];
int ans[N];
/*
int h[N],e[N],ne[N],idx,ans[N];
void add(int a,int b)//a所对应的单链表中插入b  a作为根 
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
//h[x]邻接表存储树，有n个节点，所以需要n个队列头节点
//e[x]存储元素
//ne[x]存储列表的next值
*/
void dfs(int x,int d)
{
    if(ans[x])return;
    ans[x]=d;
    for(int i=0;i<p[x].size();i++)
    {
        dfs(p[x][i],d);
    }
}
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        p[b].push_back(a);
    }
    for(int i=n;i>0;i--)
    {
        if(!ans[i])dfs(i,i);
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}
signed main(){
	IOS
	//int t;
	//cin>>t;
	int t=1;
	while(t--)
	{
		solve();
	}
}

Cow Picnic S

题目链接： https://www.luogu.com.cn/problem/P3916
题目大意： 找到所有奶牛都可达的牧场数量。
思路：
我们可以以每头牛所在的牧场为起点，去进行 dfs，对于一个牧场遍历到一次计数器加一，找到遍历次数等于 k 的牧场。这里为了防止环路需要用到 st 数组，用完记得恢复状态。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N=1e5+5;
vector<int> p[N];//用链式存储也是一样的
/*
void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
可以自己完善下
*/
int c[105];
int cnt[1005];
int ans;
int st[1005];//为了防止环路，放个st
//用st的时候不要忘记恢复状态
void dfs(int x)
{
    st[x]=1;
    cnt[x]++;
    for(int i=0;i<p[x].size();i++)
    {
        if(!st[p[x][i]])dfs(p[x][i]);
    }
}
void solve()
{
    int k,m,n;
    cin>>k>>n>>m;
    for(int i=1;i<=k;i++)
    {
        cin>>c[i];
    }
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        p[a].push_back(b);
    }
    for(int i=1;i<=k;i++){
        memset(st,0,sizeof st);
        dfs(c[i]); 
    } 
    for(int i=1;i<=n;i++)
    {
        if(cnt[i]==k)ans++;
    }
    cout<<ans;
}
signed main(){
	IOS
	//int t;
	//cin>>t;
	int t=1;
	while(t--)
	{
		solve();
	}
}

P4779 【模板】单源最短路径（标准版）

题目链接： https://www.luogu.com.cn/problem/P4779
思路：
单源最短路，无负权值，是一道 dijkstra 的题。
死去的数据结构知识在攻击我。🐒🐒
首先初始化所有节点的距离为无穷大，起点距离为 0，使用优先队列维护，优先处理距离最小的节点，遍历其所有邻接边，更新节点距离。一直重复直到队列为空。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII>> que;
const int M=2e5+5;
const int N=1e5+5;
int dis[N];//用于存储每个点到起点的最短距离
bool st[N];//用于在更新最短距离时 判断当前的点的最短距离是否确定 是否需要更新
int e[M],ne[M],h[N],idx,w[M];
void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
void dijkstra(int s)
{
    memset(dis, 0x3f, sizeof dis);
    que.push({0,s});//源点到自己距离是0；
    dis[s]=0;
    while(!que.empty())
    {
        auto x=que.top();
        que.pop();
        int dist=x.first,v=x.second;
        if(!st[v])
        {
            for(int i=h[v];i!=-1;i=ne[i])
            {
                int j=e[i];
                if(dis[j]>dist+w[i])
                {
                    dis[j]=dist+w[i];
                    que.push({dis[j],j});
                }
            }
            st[v]=true;
        }
    }
}
void solve()
{
    int n,m,s;
    cin>>n>>m>>s;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
    }
    dijkstra(s);
    for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
}
signed main(){
	IOS
	//int t;
	//cin>>t;
	int t=1;
	while(t--)
	{
		solve();
	}
}

P1144 最短路计数

题目链接： https://www.luogu.com.cn/problem/P1144
思路：
无向图，边权都是 1，这里继续使用dijkstra。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const int M=4e6+5;//这里注意无向图，二倍，不然会被被卡一个
const int N=1e6+5;
const int MOD=100003;
priority_queue<PII,vector<PII>,greater<PII>>que;
int dis[N];//用于存储每个点到起点的最短距离
int e[M],ne[M],h[N],idx,w[M];
bool st[N];
int ans[N];
void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
void dijkstra(int s)
{
    que.push({0,s});
    dis[s]=0;
    while(!que.empty())
    {
        auto x=que.top();
        que.pop();
        int dist=x.first,v=x.second;
        if(!st[v])
        {
            for(int i=h[v];i!=-1;i=ne[i])
            {
                int j=e[i];
                if(dis[j]>dist+w[i])
                {
                    dis[j]=dist+w[i];
                    ans[j]=ans[v];//路径数重置为前驱节点的路径数
                    que.push({dis[j],j});
                }else if(dis[j]==dist+w[i])
                {
                    ans[j]=(ans[v]+ans[j])%MOD;//// 累加路径数
                }
            }
            st[v]=true;
        }
    }
    
    
}
void solve()
{
    int n,m;
    cin>>n>>m;
    memset(h,-1,sizeof h);
    memset(dis,0x3f,sizeof dis);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y,1);
        add(y,x,1);
    }
    ans[1]=1;
    dijkstra(1);
    for(int i=1;i<=n;i++)
    {
        if(dis[i]==0x3f3f3f3f)cout<<"0"<<endl;
        else cout<<ans[i]<<endl;
    }
}
signed main(){
	IOS
	//int t;
	//cin>>t;
	int t=1;
	while(t--)
	{
		solve();
	}
}

P1462 通往奥格瑞玛的道路

题目链接： https://www.luogu.com.cn/problem/P1462
题目大意： 要找出满足能走通到终点的最少的钱，血量还要够，
思路：
看到最值了，考虑下二分，对于费用进行二分，对于血量用最短路。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const int M=2e5+5;
const int N=1e4+5;
int f[N];
int dis[N];//用于存储每个点到起点的血量消耗
bool st[N];//用于在更新最短距离时 判断当前的点的最短距离是否确定 是否需要更新
int e[M],ne[M],h[N],idx,w[M];
int n,m,b;
void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
bool dijkstra(int maxcost)
{
    if(f[1]>maxcost||f[n]>maxcost)return false;
    memset(st,0,sizeof st);
    memset(dis,0x3f,sizeof dis);
    priority_queue<PII,vector<PII>,greater<PII>> que;
    //从第一个城市0血出发，每经过一条边就增加对应的血量，如果血量超过b说明不行
    que.push({0,1});//源点到自己距离是0；
    dis[1]=0;
    while(!que.empty())
    {
        auto x=que.top();
        que.pop();
        int dist=x.first,v=x.second;
        if(!st[v])
        {
            for(int i=h[v];i!=-1;i=ne[i])
            {
                int j=e[i];
                if(f[j]>maxcost) continue;//钱超了
                if(dist+w[i]>b) continue;//血量超了
                if(dis[j]>dist+w[i]){
                    dis[j]=dist+w[i];
                    que.push({dis[j],j});
                }
            }
            st[v]=true;
        }
    }
    if(dis[n]<=b)return true;
    else return false;
}
void solve()
{
    cin>>n>>m>>b;
    memset(h,-1,sizeof h);
    int l=0x3f3f3f3f,r=-1;
    for(int i=1;i<=n;i++)
    {
        cin>>f[i];
        l=min(l,f[i]);
        r=max(r,f[i]);
    }
    for(int i=1;i<=m;i++)
    {
        int u,v,c;
        cin>>u>>v>>c;
        add(u,v,c);
        add(v,u,c);
    }
    int ans=-1;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(dijkstra(mid)){
            ans=mid;
            r=mid-1;
        }else l=mid+1;
    }
    if(ans!=-1)cout<<ans;
    else cout<<"AFK";
}
signed main(){
	IOS
	//int t;
	//cin>>t;
	int t=1;
	while(t--)
	{
		solve();
	}
}
  • 标题: 图上问题(并查集&dfs)与单源最短路
  • 作者: Lionlnuc
  • 创建于 : 2026-01-27 00:00:00
  • 更新于 : 2026-01-27 00:00:00
  • 链接: https://lionlnuc.github.io/2026/01/27/图上问题(并查集&dfs)与单源最短路/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
图上问题(并查集&dfs)与单源最短路
  1. 并查集模板题
  2. P2661 信息传递
  3. P3916 图的遍历
  4. Cow Picnic S
  5. P4779 【模板】单源最短路径（标准版）
  6. P1144 最短路计数
  7. P1462 通往奥格瑞玛的道路