深度优先搜索 DFS 与图的深度优先遍历

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> adj[1005];
bool vis[1005];
void dfs(int u) {
    cout << u << " ";
    vis[u] = true;
    for (int v : adj[u])
        if (!vis[v]) dfs(v);
}
int main() {
    int n, m; cin >> n >> m;
    for(int i=0;i<m;i++){
        int u,v; cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=1;i<=n;i++) sort(adj[i].begin(),adj[i].end());
    dfs(1);
    cout << endl;
}

#include <iostream>
using namespace std;
int n,m,g[105][105];
bool vis[105][105],found=false;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
void dfs(int x,int y){
    if(x==n&&y==m){found=true;return;}
    vis[x][y]=true;
    for(int d=0;d<4;d++){
        int nx=x+dx[d],ny=y+dy[d];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!g[nx][ny]&&!vis[nx][ny])
            dfs(nx,ny);
        if(found)return;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>g[i][j];
    dfs(1,1);
    cout<<(found?"YES":"NO")<<endl;
}

#include <iostream>
using namespace std;
int n,m,k,cnt=0;
int board[10][10];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};

bool canPlace(int r,int c){
    for(int d=0;d<4;d++){
        int nr=r+dx[d],nc=c+dy[d];
        if(nr>=1&&nr<=n&&nc>=1&&nc<=m&&board[nr][nc]) return false;
    }
    return true;
}

void dfs(int pos,int placed){
    if(placed==k){cnt++;return;}
    if(pos>n*m)return;
    if(n*m-pos+1<k-placed)return; // 剪枝
    int r=(pos-1)/m+1, c=(pos-1)%m+1;
    if(canPlace(r,c)){
        board[r][c]=1; dfs(pos+1,placed+1); board[r][c]=0; // 放
    }
    dfs(pos+1,placed); // 不放
}

int main(){
    cin>>n>>m>>k; dfs(1,0); cout<<cnt<<endl;
}

#include <iostream>
#include <vector>
using namespace std;
vector<int> adj[1005];
bool vis[1005];
vector<int> comp;
void dfs(int u){
    vis[u]=true; comp.push_back(u);
    for(int v:adj[u]) if(!vis[v]) dfs(v);
}
int main(){
    int n,m;cin>>n>>m;
    for(int i=0;i<m;i++){int u,v;cin>>u>>v;adj[u].push_back(v);adj[v].push_back(u);}
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            comp.clear(); dfs(i); cnt++;
            cout<<"分量"<<cnt<<": ";
            for(int x:comp) cout<<x<<" ";
            cout<<endl;
        }
    }
    cout<<"共"<<cnt<<"个连通分量"<<endl;
}

#include <iostream>
using namespace std;
int n, a[10];
bool used[10];
void dfs(int pos) {
    if (pos == n + 1) {
        for(int i=1;i<=n;i++) cout<<a[i]<<" ";
        cout<<endl;
        return;
    }
    for (int i=1; i<=n; i++) {
        if (!used[i]) {
            used[i] = true;
            a[pos] = i;
            dfs(pos + 1);
            used[i] = false; // 回溯
        }
    }
}
int main() { cin >> n; dfs(1); }

#include <iostream>
using namespace std;
int n, m, grid[105][105];
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};

void dfs(int x, int y) {
    grid[x][y] = 0; // 标记为已访问（直接改为0）
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx>=1&&nx<=n&&ny>=1&&ny<=m&&grid[nx][ny]==1)
            dfs(nx, ny);
    }
}

int main() {
    cin >> n >> m;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin >> grid[i][j];
    int cnt = 0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(grid[i][j]==1) { dfs(i,j); cnt++; }
    cout << cnt << endl;
}