[13023] ABCDE

https://www.acmicpc.net/problem/13023

13023번: ABCDE

<문제>

백트래킹 하듯 탐색하다, depth가 4가 되었을때 1을 출력한다.

 

<소스코드>

#include <bits/stdc++.h>

using namespace std;

int n, m;

vector<int> adj[2001];

bool vst[2001];

void f(int x, int cnt) {

    vst[x] = true;

    if (cnt == 4) {

        cout << 1;

        exit(0);

    }

    for (auto& nxt : adj[x]) {

        if (vst[nxt] == false) {

            vst[nxt] = true;

            f(nxt, cnt + 1);

            vst[nxt] = false;

        }

    }

}

int main(void) {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cin >> n >> m;

    int i;

    for (i = 0; i < m; i++) {

        int A, B;

        cin >> A >> B;

        adj[A].push_back(B);

        adj[B].push_back(A);

    }

    for (i = 0; i < n; i++) {

        memset(vst, 0, sizeof(vst));

        f(i, 0);

    }

    cout << 0;

    return 0;

}