문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

  • A는 B와 친구다.
  • B는 C와 친구다.
  • C는 D와 친구다.
  • D는 E와 친구다.
  • 위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

해설

단순하게 생각해보면

그래프 안에 깊이가 4이상인 트리가 존재하는지 판별하는 문제로 바꿀 수 있다.

접근방식 1 (dfs)

#include <bits/stdc++.h>
using namespace std;
vector<int> a[2001];
bool seen[2001];
void dfs(int i,int d){
    if(seen[i])return;
    if(d>3){
        cout << 1;
        exit(0);
    }
    seen[i]=1;
    for(int&v:a[i]){
        if(seen[v])continue;
        dfs(v,d+1);
    }seen[i]=0;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin >> n >> m;
    while(m--){
        int x,y;
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }for(int i=0; i<n; i++){
        dfs(i,0);
        fill(seen,seen+n,0);
    }cout << 0;
}