//In the name of Allah the most beneficent, the most merciful.
#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx,avx2,avx512,fma")
#define int long long
#define ar array
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()
#define PI 3.1415926535897932384626433832795l
const int N = 120;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
// -------------------------<RNG>-------------------------
// RANDOM NUMBER GENERATOR
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
#define SHUF(v) shuffle(all(v), RNG);
// Use mt19937_64 for 64 bit random numbers.
//--------------------------------------------------------
//int defined as long long
map<pair<int,int>,int> mp;
vector<int> adj[N];
int n,m;
int mask=0;
int vis=0;
int ed[N];
vector<int> path;
void dfs(int node){
vis|=(1<<node);
path.push_back(node);
for(auto i:adj[node])
if( ((vis&(1<<i))==0) && (mask&(1<<i)))
dfs(i);
}
bool check(){
for(int i=0;i<n;i++)
ed[i]=0;
for(int i=0;i<n;i++){
if((mask&(1<<i))==0)
continue;
for(int j=i+1;j<n;j++){
if((mask&(1<<j))==0)
continue;
ed[i]+=mp[{i,j}];
ed[j]+=mp[{i,j}];
}
}
for(int i=0;i<n;i++){
if((mask&(1<<i)) && ed[i]!=2)
return 0;
}
path.clear();
vis=0;
for(int i=0;i<n;i++)
if(mask&(1<<i)){
dfs(i);
break;
}
if(vis!=mask)
return 0;
// cout<<path.size()<<endl;
for(auto i:path)
cout<<i+1<<' ';
cout<<endl;
return 1;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
// if(n>10)
// return 0;
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
a--;
b--;
mp[{a,b}]++;
mp[{b,a}]++;
adj[a].push_back(b);
adj[b].push_back(a);
}
while(mask<(1<<n)){
mask++;
if(__builtin_popcount(mask)<4)
continue;
if(check())
return 0;
}
cout<<"no"<<endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
460 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Expected integer, but "no" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Expected integer, but "no" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |