北京化工大学数据结构2022/11/10作业 题解
我们把所有鳄鱼根据距离排序，然后开始跳，用遍历到的每一只鳄鱼更新其他鳄鱼的dist值。首先一定整张图一定要连通（这是废话，但得判断一下，也就是ans==1的部分）（在并查集中，有几个fa[i]=i，证明有几个连通块，没听过可以了解一下）我们只要从起点dfs一遍，如果还有没到过的点，说明不是连通图，在输出一个0。欧拉回路可以有很多方法求，dfs不是很好写，这里给出一种并查集的求法。原题要想ac是要t
·
---------------------------------------------------------------------------------------------------------------------------------
如果以前没怎么写过dfs，一头雾水的
晚上睡不着肝了个->
(15条消息) 彻底搞懂dfs与回溯_lxrrrrrrrr的博客-CSDN博客
希望这里面能说明白哈
目录
问题 A: 将邻接矩阵存储的图转换为邻接表存储的图，附加代码模式
问题 B: 邻接表存储的图转化为邻接矩阵存储的图-附加代码模式
问题 D: 邻接矩阵存储图的DFS-非递归算法（附加代码模式）
问题 G: 邻接矩阵存储图的DFS完成序求解（附加代码模式）
问题 A: 将邻接矩阵存储的图转换为邻接表存储的图，附加代码模式
纯纯大模拟
数据同学交python吧
cpp代码：
#include <iostream>
using namespace std;
#define MAX_SIZE 100
struct Graph{
int vexNumber;
string info[MAX_SIZE];
int adjMatrix[MAX_SIZE][MAX_SIZE];
};
struct ArcNode
{
int weight;
int adj;
ArcNode *nextarc;
};
struct VexNode
{
string Info;
ArcNode *firstarc;
};
struct linkGraph
{
VexNode *vexes;
int vexnumber;
};
int InitGraph(linkGraph &G,int vexnumber)
{
G.vexes=new VexNode[vexnumber];
G.vexnumber=vexnumber;
for(int i=0;i<vexnumber;++i)
{
G.vexes[i].firstarc=nullptr;
return 0;
}
}
void InitGraph(linkGraph &G,const Graph& g)
{
int n=g.vexNumber;
int flag[n]={0};
InitGraph(G,n);
for(int i=0;i<g.vexNumber;i++)
{
G.vexes[i].Info=(char)(i+'a');
for(int j=0;j<g.vexNumber;++j)
{
if(g.adjMatrix[i][j]!=0)
{ArcNode *p=new ArcNode;
p->nextarc=G.vexes[i].firstarc;
G.vexes[i].firstarc=p;
p->adj=j;}
}
}
}
int DestroyGraph(linkGraph &G)
{
for(int i=0;i<G.vexnumber;i++)
{
while(G.vexes[i].firstarc!=nullptr)
{
ArcNode *p=G.vexes[i].firstarc;
G.vexes[i].firstarc=p->nextarc;
delete p;
}
}
delete[]G.vexes;
G.vexes=nullptr;
G.vexnumber=0;
return 0;
}
void PrintGraph(const linkGraph &G){
for(int i=0;i<G.vexnumber;++i)
{
cout<<G.vexes[i].Info;
ArcNode *p=G.vexes[i].firstarc;
while(p)
{
cout<<" --> "<<G.vexes[p->adj].Info;
p=p->nextarc;
}
cout<<"\n";
}
}python代码：
n=int(input())
g=[]
for i in range(0,n):
s=input().split()
g.append(s)
for i in range(0,n):
result=ord('a')+i
result=[chr(result)]
for j in range(n-1,-1,-1):
if g[i][j]=='1':
result.append(chr(ord('a')+j))
print(' --> '.join(result))问题 B: 邻接表存储的图转化为邻接矩阵存储的图-附加代码模式
cpp代码：
#include<bits/stdc++.h>
#include<queue>
#include<stack>
using namespace std;
#define size 100;
struct Graph{
int vexNumber;
string info[100];
int adjMatrix[100][100];
};//邻接矩阵存储的图
struct ArcNode{
char weight;//弧上的信息
int adj;//序号
ArcNode* nextarc;
};//弧结点定义
struct VexNode{
char Info;//顶点信息
VexNode* nextarc;
};
struct linkGraph{
VexNode *vexes;
int vexnumber;
int Matrix[100][100];
};
ArcNode* getArcNode(int adj){
ArcNode* node=new ArcNode();
return node;
}
void InputlinkGraph(linkGraph& lg){
int n;
cin>>n;
lg.vexnumber=n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
lg.Matrix[i][j]=0;
}
}
char str[10];
while(n--){
cin>>str;
char c=str[0];
for(int i=1;i<strlen(str);i++){
if(str[i]!='-'){
lg.Matrix[c-'a'][str[i]-'a']=1;
}
}
}
return;
}
void linkGraph2Graph(const linkGraph&lg,Graph& g){
return;
}
void printGraph(const Graph&g){
return;
}
void PrintlinkGraph(linkGraph&g){
for(int i=0;i<g.vexnumber;i++){
cout<<(char)('a'+i)<<" ";
for(int j=g.vexnumber-1;j>=0;j--){
if(g.Matrix[i][j]==1){
cout<<"--> ";
cout<<(char)('a'+j)<<" ";
}
}cout<<endl;
}
for(int i=0;i<g.vexnumber;i++){
for(int j=0;j<g.vexnumber;j++){
cout<<g.Matrix[i][j]<<" ";
}
cout<<endl;
}
return;
}
int DestroylinkGraph(linkGraph&g){
return 0;
}python代码：
n=int(input())
v=[]
g=[]
for i in range(0,n):
g.append([0]*n)
for i in range(0,n):
v.append(input().split('-'))
for i in range(0,n):
begin = v[i][0]
for j in range(1,len(v[i])):
ind=ord(v[i][j])-ord('a')
g[i][ind]=1
for i in range(0,n):
print(' --> '.join(v[i]))
for i in range(0,n):
print(' '.join(map(str,g[i])))问题 C: 邻接矩阵存储图的DFS（附加代码模式）
dfs板子
#include <bits/stdc++.h>
using namespace std;
#define MAXSIZE 100
// 邻接矩阵存储的图型数据结构
struct Graph{
int vexNumber;
string vexInfo[MAXSIZE];
int adjMatrix[MAXSIZE][MAXSIZE];
};
void DFS(Graph G, int v, int st[]){
cout<<G.vexInfo[v]<< " ";
st[v] = 1;
for(int i=0;i<G.vexNumber;i++){
if(!st[i] && G.adjMatrix[v][i] == 1){
DFS(G,i,st);
}
}
}
void DFS(Graph G){
int st[150];
memset(st,0,sizeof st);
for(int i=0;i<G.vexNumber;i++){
if(!st[i]){
DFS(G, i , st);
}
}
}问题 D: 邻接矩阵存储图的DFS-非递归算法（附加代码模式）
#include <iostream>
#include <string>
#include <cstdio>
#include <stack>
#include <queue>
using namespace std;
#define MAX_SIZE 100
// 邻接矩阵存储的图
struct Graph
{
int vexNumber;
string vexInfo[MAX_SIZE];
int adjMatrix[MAX_SIZE][MAX_SIZE];
};
// 查找v0的未被访问的邻接点
int findAdjVex(const Graph& G, int v0, int visited[]){
for (int i=0;i<G.vexNumber;++i){
if (G.adjMatrix[v0][i]==1 && !visited[i]) {
return i;
}
}
return -1;
}
// 以顶点v0为起点，进行一趟DFS
string DFS(const Graph& G, int v0, int visited[]){
string result = G.vexInfo[v0];
visited[v0] = 1;
int adj;
while ((adj = findAdjVex(G, v0, visited)) != -1) {
result += " ";
result += DFS(G, adj, visited);
}
return result;
}
// 对整个图进行DFS
string DFS(const Graph& G){
string result = "";
// 第一步：初始化visited数组
int visited[MAX_SIZE] = { 0 };
// 第二步：以每个未被遍历的顶点为起点，进行DFS
for (int i = 0; i < G.vexNumber; ++i) {
if (!visited[i]) {
result += DFS(G, i, visited);
}
}
return result;
}问题 E: 邻接矩阵存储图的BFS
bfs板子，只不过是邻接矩阵的
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et cout<<'\n'
#define xx first
#define yy second
using namespace std;
template <typename _Tp>void input(_Tp &x){
char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
const int N=1e6+10;
int M[60][60];
bool st[60];
int n;
void bfs(int i){
queue<int> q;
q.push(i);
while(q.size()){
auto t=q.front();
q.pop();
for(int i=0;i<n;++i){
if(M[t][i]&&!st[i]){
cout<<i<<" ";
q.push(i);
st[i]=1;
}
}
}
}
signed main()
{
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>M[i][j];
}
}
for(int i=0;i<n;i++){
if(!st[i]){
st[i]=1;
cout<<i<<' ';
bfs(i);
}
}
}问题 F: 案例6-1.2：邻接表存储图的广度优先遍历
这题也注意下排序，然后就是bfs板子了
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et cout<<'\n'
#define xx first
#define yy second
using namespace std;
template <typename _Tp>void input(_Tp &x){
char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
const int N=1e6+10;
vector<int> v[N];
int vis[N];
void bfs(int x){
queue<int>q;
q.push(x);
while(q.size()){
int now=q.front();
q.pop();
if(vis[now]==1) continue;
vis[now]=1;
cout<<now<<" ";
for(auto t:v[now]){
if(vis[t]) continue;
q.push(t);
}
}
}
signed main(){
int n,m,x;
input(n,m,x);
fer(i,1,m){
int a,b;
input(a,b);
v[a].push_back(b);
v[b].push_back(a);
}
fer(i,0,n-1){
sort(v[i].begin(),v[i].end());
}
bfs(x);
}问题 G: 邻接矩阵存储图的DFS完成序求解（附加代码模式）
裸dfs
#include <iostream>
#include <string>
#include <cstdio>
#include <stack>
#include <queue>
using namespace std;
#define MAX_SIZE 100
struct Graph
{
int vexNumber;
string vexInfo[MAX_SIZE];
int adjMatrix[MAX_SIZE][MAX_SIZE];
};
int findAdjVex(const Graph& G, int v0, int visited[]){
return 0;
}
string DFS_finished(const Graph &G, int v0, int visited[]){
string res="";
visited[v0]=1;
for(int i=0;i<G.vexNumber;i++){
if(G.adjMatrix[v0][i]==1&& !visited[i]){
res+=DFS_finished(G,i,visited);
}
}
res+=(char)(v0+'a');
return res;
}
string DFS_finished(const Graph &G){
string res="";
int n=G.vexNumber;
int visited[MAX_SIZE]={};
for(int i=0;i<n;i++){
if(!visited[i]) res+=DFS_finished(G,i,visited);
}
return res;
}问题 H: 案例6-1.1：DFS应用-计算可达城市对
这题数据比较小，相当于dfs板子题了
对于每个点dfs一遍统计答案
这道题的进阶版[JSOI2010]连通数 - 洛谷
原题是要tarjan缩点的，有兴趣的同学可以研究下
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et cout<<'\n'
#define xx first
#define yy second
using namespace std;
template <typename _Tp>void input(_Tp &x){
char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
const int N=1e6+10;
using namespace std;
vector<int> v[N];
bool vis[N];
int m,n;
int dfs(int x){
int res=1;
vis[x]=1;
for(auto t:v[x]){
if(!vis[t]){
res+=dfs(t);
}
}
return res;
}
signed main(){
int ans=0;
input(n,m);
int x,y;
fer(i,1,m){
input(x,y);
v[x].pb(y);
}
fer(i,1,n){
memset(vis,0,sizeof vis);
ans+=dfs(i);
}
cout<<ans;
}问题 I: 案例6-1.3：哥尼斯堡的“七桥问题”
欧拉回路：每条边都要经过一次，并且回到出发点
欧拉回路可以有很多方法求，dfs不是很好写，这里给出一种并查集的求法
不懂并查集可以搜一下
首先一定整张图一定要连通（这好像是废话，但得判断一下，也就是ans==1的部分）
（在并查集中，有几个fa[i]=i，证明有几个连通块，没听过可以了解一下）
其次，所有点的度必须为偶数（度：无向图中一个点连有几条边度就是几）
因为欧拉回路既然是回路就得一来一回，奇数肯定不行
满足这俩条件就是有欧拉回路
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et cout<<'\n'
#define xx first
#define yy second
using namespace std;
template <typename _Tp>void input(_Tp &x){
char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
const int N=1e6+10;
int fa[N];
int find(int x){
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
int w[N];
signed main()
{
int n,m;
fer(i,0,1000) fa[i]=i;
input(n,m);
while(m--)
{
int a,b;
input(a,b);
if(find(a)!=find(b)){
fa[find(a)]=find(b);
}
w[a]++;
w[b]++;
}
int ans=0;
int flag=1;
fer(i,1,n)
{
if(w[i]%2!=0){
flag=0;
}
if(fa[i]==i){
ans++;
}
}
if(ans!=1){
flag=0;
}
if(flag){
cout<<"1"<<'\n';
}
else{
cout<<"0"<<'\n';
}
}问题 J: 案例6-1.4：地下迷宫探索
这题注意dfs的时候排下序
我们只要从起点dfs一遍，如果还有没到过的点，说明不是连通图，在输出一个0
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et cout<<'\n'
#define xx first
#define yy second
using namespace std;
template <typename _Tp>void input(_Tp &x){
char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
const int N=1e4+10;
int n,m,st;
vector<int >v[N];
stack<int>s;
bool vis[N];
void dfs(int k)
{
vis[k]=1;
sort(v[k].begin(),v[k].end());
for(auto t:v[k]){
if(!vis[t]){
s.push(k);
cout<<t<<" ";
dfs(t);
}
}
if(k!=st)
{
cout<<s.top()<<' ';
s.pop();
}
}
signed main()
{
input(n,m,st);
fer(i,1,m)
{
int a,b;
input(a,b);
v[a].push_back(b);
v[b].push_back(a);
}
cout<<st<<" ";
dfs(st);
fer(i,1,n)
{
if(!vis[i])
{
cout<<0;
break;
}
}
}问题 K: 基础实验6-2.3：拯救007
可以dfs也可以bfs，这里给出其中一种bfs的写法
我们把所有鳄鱼根据距离排序，然后开始跳，用遍历到的每一只鳄鱼更新其他鳄鱼的dist值
直至可以跳出或不能再跳
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et cout<<'\n'
#define xx first
#define yy second
using namespace std;
template <typename _Tp>void input(_Tp &x){
char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
const int N=1e5+10;
int n,r;
int dist[N];
const int INF=0x3f3f3f3f;
struct Node{
int x,y;
double dis;
};
Node node[N];
bool cmp(Node &a,Node &b){
return a.dis<b.dis;
}
void bfs(){
queue<int> q;
for(int i=0;i<n;i++){
if(node[i].dis>7.5&&node[i].dis<=7.5+r){
q.push(i);
dist[i]=1;
}
}
while(q.size()){
int u=q.front();
q.pop();
double nex=min(50-abs(node[u].x),50-abs(node[u].y));
if(nex<=r){
dist[n]=dist[u]+1;
break;
}
for(int i=0;i<n;i++){
if(dist[i]==INF){
double next=sqrt((node[i].x-node[u].x)*(node[i].x-node[u].x)+(node[i].y-node[u].y)*(node[i].y-node[u].y));
if(next<=r){
dist[i]=dist[u]+1;
q.push(i);
}
}
}
}
}
signed main(){
fer(i,0,105) dist[i]=INF;
input(n,r);
if(r>=43){
cout<<"Yes"<<'\n';
return 0;
}
fer(i,0,n-1){
input(node[i].x,node[i].y);
node[i].dis=sqrt(node[i].x*node[i].x+node[i].y*node[i].y);
}
sort(node,node+n,cmp);
bfs();
if(dist[n]!=INF){
cout<<"Yes"<<'\n';
}
else{
cout<<"No"<<'\n';
}
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
10
0- 0
已为社区贡献4条内容
所有评论(0)