ABCDE (feat. 백준, 13023번)

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

13023번: ABCDE

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <map>
#include <set>
using namespace std;
map<int, set<int>> arr;
bool visit[2000];
int flag;
void dfs(register int cnt, register int idx){
    if(cnt == 4){
        flag = true;
        return;
    }
    for(auto& v : arr[idx])
        if(!visit[v]){
            visit[v] = true;
            dfs(cnt + 1, v);
            visit[v] = false;
            if(flag)
                return;
        }
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, M;
    cin >> N >> M;
    flag = false;
    memset(visit, false, N);
    for(register int m = 0, a, b; m < M; ++m)
        cin >> a >> b, arr[a].insert(b), arr[b].insert(a);
    for(register int n = 0; n < N; ++n){
        visit[n] = true;
        dfs(0, n);
        visit[n] = false;
        if(flag){
            cout << 1;
            return 0;
        }
    }
    cout << 0;
	return 0;
}
// *&)*@*

 

반응형

A와 B는 친구이므로 arr[A]에는 B가 있어야 하고 arr[B]에도 A가 있어야 합니다.

또한 그 관계가 A->B->C->D->E 로 아무나 5명의 연결된 친구가 있다면 1을 출력합니다. (총 4번의 친구 관계입니다.)