M11D30

deepshits · 2025-11-30 10:15:57 · 个人记录

邻接矩阵dfs

#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

#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

#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;
}

公司数量

#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;
}

一笔画问题

#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

#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

#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

#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