一些图论模版题题解
  • 板块学术版
  • 楼主CZQ_caozhaoqi
  • 当前回复1
  • 已保存回复2
  • 发布时间2024/7/9 19:12
  • 上次更新2024/7/9 19:21:35
查看原帖
一些图论模版题题解
1321799
CZQ_caozhaoqi楼主2024/7/9 19:12

前言

首先感谢审核员审核过我の帖子，本文是一些图论模版题题解（可能不是特别详细，可以去看对应题题解）

深搜/广搜模板

P5318 【深基18.例3】查找文献

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
int n,m;
vector<int> G[N];
bool vis[N];
void dfs(int u)
{
	cout << u << ' ';//输出当前节点
	vis[u] = 1;//标记已经访问过
	for(int i = 0;i < G[u].size();i++)//遍历当前节点的所有邻接点
	{
		if(!vis[G[u][i]])// 如果邻接点没有被访问过
		{
			dfs(G[u][i]);// 递归访问邻接点
		}
	}
}
void bfs(int root)
{
	queue<int> q;//创建一个队列
	q.push(root);//将起始节点放入队列 
	vis[root] = 1;//标记已经访问过
	while(!q.empty())//当队列不为空
	{
		int u = q.front();//取出队首元素
		q.pop();//弹出队首元素
		cout << u << ' ';
		for(int i = 0;i < G[u].size();i++)//遍历当前节点的所有邻接点
		{
			if(vis[G[u][i]]) continue;// 如果邻接点没有被访问过
			q.push(G[u][i]);//将邻接点放入队列
			vis[G[u][i]] = 1;//标记已经访问过
		}
	}
}
signed main()
{
	cin >> n >> m;
	for(int i = 1;i <= m;i++)
	{
		int u,v;
		cin >> u >> v;
		G[u].push_back(v);
	}
	for(int i = 1;i <= n;i++)
	{
		sort(G[i].begin(),G[i].end());
	}
	dfs(1);
	cout << endl;
	memset(vis,0,sizeof(vis));
	bfs(1);
	return 0;
}

拓扑排序

B3644 【模板】拓扑排序 / 家谱树

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 105;
int n;
int in[N];
vector<int> G[N];
signed main()
{
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		int x;
		while(cin >> x)
		{
			if(!x) break;
			G[i].push_back(x);
			in[x] ++;
		}
	}
	queue<int> q;
	for(int i = 1;i <= n;i++)
	{
		if(!in[i]) q.push(i);
	}
	while(!q.empty())
	{
		int u = q.front();
		cout << u << ' ';
		q.pop();
		for(auto i : G[u])
		{
			in[i] --;
			if(!in[i])
			{
				q.push(i);
			}
		}
	}
	return 0;
}

最小生成树(kruskal)

P3366 【模板】最小生成树

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5;
int n,m;
struct edge{
	int u,v,w;
}e[N];
bool cmp(edge a,edge b)
{
	return a.w < b.w;
}
int fa[N];
int find(int x)
{
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void kruskal()
{
	sort(e + 1, e + m + 1,cmp);
	int cnt = 0,ans = 0;
	for(int i = 1;i <= m;i++)
	{
		int u = e[i].u,v = e[i].v,w = e[i].w;
		int fu = find(u),fv = find(v);
		if(fu == fv) continue;
		ans += w;
		cnt ++;
		fa[fu] = fv;
		if(cnt == n - 1) break;
	}
	if(cnt < n - 1) cout << "orz\n";
	else cout << ans << endl;
}
signed main()
{
	cin >> n >> m;
	for(int i = 1;i <= max(n,m);i++) fa[i] = i;
	for(int i = 1;i <= m;i++)
	{
		int x,y,z;
		cin >> x >> y >> z;
		e[i] = {x,y,z};
	}
	kruskal();
	return 0;
}

并查集

P3367 【模板】并查集

T471653 并查集（数据加强版）

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e4 + 5;
int n,m;
int fa[N];
int find(int x)
{
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
signed main()
{
	cin >> n >> m;
	for(int i = 1;i <= n;i++) fa[i] = i;
	while(m--)
	{
		int op,x,y;
		cin >> op >> x >> y;
		if(op == 1)
		{
			fa[find(x)] = find(y);
		}
		else
		{
			int fx = find(x);
			int fy = find(y);
			cout << ((fx == fy) ? 'Y' : 'N');
			cout << "\n";
		}
	}
	return 0;
}

单源最短路

  • bellman-ford(一点用没有，只能做弱化)

    P3371 【模板】单源最短路径（弱化版）

    #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 5;
vector<int> G[N];
int f[N][20];
int dep[N];
void dfs(int u,int fa)
{
   dep[u] = dep[fa] + 1;
   f[u][0] = fa;
   for(int i = 1;(1 << i) < dep[u];i++) f[u][i] = f[f[u][i - 1]][i - 1];
   for(auto v : G[u])
   {
       if(v == fa) continue;
       dfs(v,u);
   }
}
int lca(int u,int v)
{
   if(dep[u] < dep[v]) swap(u,v);
   for(int i = 19;i >= 0;i--)
   {
       if(dep[f[u][i]] >= dep[v]) u = f[u][i];
   }
   if(u == v) return u;
   for(int i = 19;i >= 0;i--)
   {
       if(f[u][i] == f[v][i]) continue;
       u = f[u][i];
       v = f[v][i];
   }
   return f[u][0];
}
signed main()
{
   int n,m,s;
   scanf("%d%d%d",&n,&m,&s);
   for(int i = 1;i < n;i++)
   {
       int u,v;
       scanf("%d%d",&u,&v);
       G[u].push_back(v);
       G[v].push_back(u);
   }
   dfs(s,0);
   while(m--)
   {
       int u,v;
       scanf("%d%d",&u,&v);
       printf("%d\n",lca(u,v));
   }
   return 0;
}

  • dijkstra

    #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 5;
struct edge{
    int to,w,nxt;
}e[N];
bool vis[N];
struct node{
    int u,dis;
    bool operator <( const node &x )const
    {
        return x.dis < dis;
    }
};
int n,m,s;
int tot;
int head[N];
void add(int u,int v,int w)
{
    e[tot].w = w;
    e[tot].to = v;
    e[tot].nxt = head[u];
    head[u] = tot++;
}
int dis[N];
void dijkstra()
{
    memset(dis,0x3f,sizeof(dis));
    dis[s] = 0;
    priority_queue<node> q;
    node t = {s,0};
    q.push(t);
    while(!q.empty())
    {
        t = q.top();
        q.pop();
        int now = t.u;
//		cout << now << endl;
        if(vis[now]) continue;
        vis[now] = 1;
        for(int i = head[now];~i;i = e[i].nxt)
        {
            int v = e[i].to;
            if(dis[v] > dis[now] + e[i].w)
            {
                dis[v] = dis[now] + e[i].w;
                if(vis[v]) continue;
                t = {v,dis[v]};
                q.push(t);
            }
        }
    }
    for(int i = 1;i <= n;i++) cout << dis[i] << ' ';
    cout << endl;
}
signed main()
{
    memset(head,-1,sizeof(head));
    cin >> n >> m >> s;
    for(int i = 1;i <= m;i++)
    {
        int u,v,w;
        cin >> u >> v >> w;
        add(u,v,w);
    }
    dijkstra();
    return 0;
}

Floyd

B3647 【模板】Floyd

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100 + 5;
int n,m;
int dis[N][N];
signed main()
{
	cin >> n >> m;
	memset(dis,0x3f,sizeof(dis));
	for(int i = 1;i <= m;i++)
	{
		int u,v,w;
		cin >> u >> v >> w;
		dis[u][v] = min(dis[u][v],w);
		dis[v][u] = min(dis[v][u],w);
	}
	for(int i = 1;i <= n;i++) dis[i][i] = 0;
	for(int k = 1;k <= n;k++)
	{
		for(int i = 1;i <= n;i++)
		{
			for(int j = 1;j <= n;j++)
			{
				dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
			}
		}
	}
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= n;j++) cout << dis[i][j] << ' ';
		cout << endl;
	}
	return 0;
}

欧拉路径

P7771 【模板】欧拉路径

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5;
int n,m; 
vector<int> G[N];
struct drop{
	int in,out;
}e[N];
drop sum;
int stk[N];
int tot;
int del[N];
void dfs(int u)
{
//	cout << u << endl;
//	cout << del[u] << ' ' << (int)G[i].size() << endl;
	for(int i = del[u];i < G[u].size();i = del[u])
	{
		del[u] = i + 1;
//		cout << G[u][i] << endl;
		dfs(G[u][i]);
	}
	stk[++tot] = u;
}
signed main()
{
	cin >> n >> m;
	for(int i = 1;i <= m;i++)
	{
		int u,v;
		cin >> u >> v;
		G[u].push_back(v);
		e[u].out++;
		e[v].in++;
	}
	for(int i = 1;i <= n;i++)
	{
		sort(G[i].begin(),G[i].end());
	}
	int start = 1;
	for(int i = 1;i <= n;i++)
	{
		int in = e[i].in,out = e[i].out;
		if(in == out) continue;
		if(out > in)
		{
			sum.out++;
			if(out - in != 1 || sum.out > 1) 
			{
				cout << "No\n";
				return 0;
			}
			start = i;
		}
		else
		{
			sum.in++;
			if(in - out != 1 || sum.in > 1)
			{
				cout << "No\n";
				return 0;
			}
		}
	}
//	cout << start << endl;
	if(sum.out != sum.in || sum.in > 1 || sum.out > 1) 
	{
		cout << "No\n";
		return 0;
	}
	dfs(start);
	for(int i = tot;i >= 1;i--) cout << stk[i] << ' ';
	return 0;
}

后记

本人能力有限，难免有错，欢迎大家指正

点个赞再走呗qwq

2024/7/9 19:12