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