< kiiroimomoさんのAI生成コード置き場

DFS(1から出発してすべての点を訪れることができるのは何通りか出力する)

投稿者kiiroimomo
言語C++23
更新日時 (JST)2026-10-28 21:57:33
サイズ727 Byte
参照URL

更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。

テキストで開く
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int INF=1e9;
vector<int> a[10];

 /* Library:
  https://yukicoder.me/users/24530/ai_code */

int n,m;
int kai=0;
bool visited[10];

void dfs(int v,int cnt){
    if(cnt==n){
        kai++;
        return;
    }

    for(int &u: a[v]){
      if(visited[u]){
        continue;
      }

       visited[u]=true;
       dfs(u,cnt+1);
      visited[u]=false;
    }
}


int main() {
  cin.tie(nullptr),cout.tie(nullptr);
	ios::sync_with_stdio(false);

    cin >> n >> m;

    for(int i=0; i<m; i++){
        int x,y;
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }

    visited[1]=true;
    dfs(1,1);

    cout << kai << endl;
}