الگوریتم های نمایی پیدا کردن دور و مسیر همیلتونی¶

#define bit(n,k) (((n)>>(k))&1)

const int maxn = 16;

bool dp[1<<maxn][maxn][maxn];
bool adj[maxn][maxn];

int main(){
    // voroodi gereftan graph
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
      for(int j = 0; j < n; j++)
          cin >> adj[i][j];

    // mohasebe dp
    for(int mask = 1; mask < (1<<n); mask++){
        if(__builtin_popcount(mask) == 1){
            dp[mask][__builtin_ctz(mask)][__builtin_ctz(mask)] = 1;
            continue;
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                  if(i == j || bit(mask, i) == 0 || bit(mask, j) == 0)
                      continue;
                  for(int k = 0; k < n; k++){
                      if(k == j || bit(mask, k) == 0 || adj[k][j] == 0)
                              continue;
                      dp[mask][i][j] |= dp[mask ^ (1<<j)][i][k];
                  }
            }
        }
    }
    bool ans = 0;
    for(int i = 0; i < n; i++)
           for(int j = 0; j < n; j++)
               ans |= dp[(1<<n)-1][i][j];

    if(ans)
            cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}

#define bit(n,k) (((n)>>(k))&1)

const int maxn = 16;

int dp[1<<maxn][maxn];
bool adj[maxn][maxn];

int main(){
    // voroodi gereftan graph
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
                cin >> adj[i][j];
    // mohasebe dp
    for(int mask = 1; mask < (1<<n); mask++){
           if(__builtin_popcount(mask) == 1){
            dp[mask][__builtin_ctz(mask)] = mask;
            continue;
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i == j || bit(mask, i) == 0 || bit(mask, j) == 0 || adj[i][j] == 0){
                    continue;
                }
                dp[mask][i] |= dp[mask ^ (1<<i)][j];
            }
        }
    }
    bool ans = 0;
    for(int i = 0; i < n; i++)
        if(dp[(1<<n)-1][i] != 0){
            ans = 1;
    if(ans)
        cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}

#include<bits/stdc++.h>

#define bit(n,k) (((n)>>(k))&1)

using namespace std;

const int maxn = 16;

bool dp[1<<maxn][maxn];
bool adj[maxn][maxn];

int main(){
    // voroodi gereftan graph
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> adj[i][j];
    // mohasebe dp
    for(int mask = 1; mask < (1<<n); mask++){
        if(__builtin_popcount(mask) == 1){
            dp[mask][__builtin_ctz(mask)] = 1;
            continue;
        }
        int low_bit = __builtin_ctz(mask);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i == j || bit(mask, i) == 0 || bit(mask, j) == 0 || i == low_bit || adj[i][j] == 0)
                    continue;
                dp[mask][i] |= dp[mask ^ (1<<i)][j];
            }
        }
    }
    bool ans = 0;
    for(int i = 1; i < n; i++){ // i != 0
        if(dp[(1<<n)-1][i] && adj[0][i])
            ans = 1;
    }
    if(ans)
        cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}

#define bit(n,k) (((n)>>(k))&1)

const int maxn = 16;

int dp[1<<maxn];
int adj_mask[maxn];

int main(){

    // voroodi gereftan graph
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            bool x;
            cin >> x;
            if(x){
                adj_mask[i] |= 1<<j;
            }
        }
    }
    // mohasebe dp
    for(int mask = 1; mask < (1<<n); mask++){
        if(__builtin_popcount(mask) == 1){
            dp[mask] = mask;
            continue;
        }
        int low_bit = __builtin_ctz(mask);
        for(int i = 0; i < n; i++){
            if(bit(mask, i) == 0 || i == low_bit)
                continue;
            if(dp[mask ^ (1<<i)] & adj_mask[i])
                dp[mask] |= 1<<i;
        }
    }
    bool ans = 0;
    if(dp[(1<<n)-1] != 0)
        ans = 1;
    if(ans)
        cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}