专栏文章

M11D30

ddeepshits
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimxuiyw
此快照首次捕获于
2025/12/01 17:19
3 个月前
此快照最后确认于
2025/12/01 17:19
3 个月前
查看原文

邻接矩阵dfs

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
int g[1001][1001];
bool vis[1005];
void dfs(int i){
	cout<<i<<' ';
	vis[i]=1;
	for(int j=1;j<=n;j++){
		if(vis[j]==0&&g[i][j]==1)
		    dfs(j);
	}
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	int u,v;
    	cin>>u>>v;
    	g[u][v]=1;
    	g[v][u]=1;
	}
	dfs(1);
	return 0;
}

vector dfs

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> g[1005];
bool vis[1001];
void dfs(int i){
	cout<<i<<' ';
	vis[i]=1;
	for(auto j:g[i]){
	    if(vis[j]==0){
		    dfs(j);
	    }
	}
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	int u,v;
    	cin>>u>>v;
    	g[u].push_back(v);
    	g[v].push_back(u);
	}
	dfs(1);
	return 0;
}

链式前向星dfs

CPP
#include<bits/stdc++.h>
using namespace std;
struct node{
	int nxt;
	int to;
}g[1001];
int n,m;
int len;
int head[1005];
void add(int u,int v){
	len++;
	g[len].to=v;
	g[len].nxt=head[u];
	head[u]=len;
}
bool vis[105];
void dfs(int i){
	cout<<i<<' ';
	vis[i]=1;
	for(int j=head[i];j!=0;j=g[j].nxt){
		if(vis[j]==0)
		    dfs(j);
	}
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	int x,y;
    	cin>>x>>y;
    	add(x,y);
    	add(y,x);
	}
	dfs(1);
	return 0;
}

公司数量

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> g[1005];
bool vis[1001];
void dfs(int i){
	vis[i]=1;
	for(auto j:g[i]){
	    if(vis[j]==0){
		    dfs(j);
	    }
	}
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	int u,v;
    	cin>>u>>v;
    	g[u].push_back(v);
    	g[v].push_back(u);
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
	    if(vis[i]==0){
	    	cnt++;
	    	dfs(i);
		}
	cout<<cnt<<endl;
	return 0;
}

一笔画问题

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> g[1005];
bool vis[1001];
int du[1001];
void dfs(int i){
	cout<<i<<' ';
	vis[i]=1;
	for(auto j:g[i]){
	    if(vis[j]==0){
		    dfs(j);
	    }
	}
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	int u,v;
    	cin>>u>>v;
    	g[u].push_back(v);
    	g[v].push_back(u);
    	du[u]++,du[v]++;
	}
	int cnt=0;
	int st=1;
	for(int i=1;i<=n;i++){
		if(du[i]%2==1){
			cnt++;
			st=i;
		}
	}
	if(cnt==0||cnt==2){
		dfs(st);
		if(cnt==0)cout<<st;
	}
	return 0;
}

邻接矩阵bfs

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
int g[1001][1001];
bool vis[1005];
int q[1005];
int head,tail;
void bfs(int st){
	q[++tail]=st;
	cout<<st;
	vis[st]=1;
	while(head<tail){
		int i=q[++head];
		for(int j=1;j<=n;j++){
			if(vis[j]==0&&g[i][j]==1){
				cout<<' '<<j;
				q[++tail]=j;
				vis[j]=1;
			}
		}
	}
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	int u,v;
    	cin>>u>>v;
    	g[u][v]=1;
    	g[v][u]=1;
	}
	bfs(1);
	return 0;
}

vectorbfs

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> g[1005];
bool vis[1001];
int q[1001];
int head,tail;
void bfs(int st){
	q[++tail]=st;
	vis[st]=1;
	while(head<tail){
		int i=q[++head];
		cout<<i<<' ';
		for(auto j:g[i]){
			if(vis[j]==0){
				q[++tail]=j;
				vis[j]=1;
			}
		}
	}
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	int u,v;
    	cin>>u>>v;
    	g[u].push_back(v);
    	g[v].push_back(u);
	}
	bfs(1);
	return 0;
}

链式前向星bfs

CPP
#include<bits/stdc++.h>
using namespace std;
struct node{
	int nxt;
	int to;
}g[1001];
int n,m;
int len;
int head[1005];
void add(int u,int v){
	len++;
	g[len].to=v;
	g[len].nxt=head[u];
	head[u]=len;
}
int h,t;
int q[1005];
bool vis[105];
void bfs(int st){
	q[++t]=st;
	vis[st]=1;
	while(h<t){
		int i=q[++h];
		cout<<i<<' ';
		for(int j=head[i];j!=0;j=g[j].nxt){
			if(vis[g[j].to]==0){
				q[++t]=g[j].to;
				vis[g[j].to]=1;
			}
		}
	}
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	int x,y;
    	cin>>x>>y;
    	add(x,y);
    	add(y,x);
	}
	bfs(1);
	return 0;
}

题目：

P5318 P1636

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...