https://www.acmicpc.net/problem/13023
요구사항 : A-B-C-D-E의 관계가 존재하는지 확인
A-B-C-D-E의 관계란? 깊이가 5인 그래프가 존재 하는지 확인
예제 1을 그려보면 다음과 같다.
0을 기준으로 보면 0-1-2-3-4 즉 A-B-C-D-E의 관계가 성립한다.
1을 기준으로 보면 1-0의 관계와 1-2-3-4의 관계로 A-B-C-D-E의 관계는 성립하지 않는다.
4를 기준으로 봐도 4-3-2-1-0으로 A-B-C-D-E의 관계가 성립된다.
하지만 해당 문제에서 요구하는 것은 해당 관계가 존재하는지만 확인하는 것이므로 그냥 0을 기준으로 확인하고 뒤는 확인 하지 않고 출력후 종료하면된다.
코드
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<vector<int>> A;
vector<bool> visited;
bool ok =false;
void dfs(int st, int cnt){
if(cnt==5||ok){
ok=true;
return ;
}
visited[st] = true;
for(auto i : A[st]){
if(i==-1)continue;
if(!visited[i]){
dfs(i,cnt+1);
}
}
visited[st]=false;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
//배열 초기화
A.resize(n);
//방문을 확인하는 배열
for(int i=0; i<n; i++)visited.push_back(false);
//
for(int i=0; i<m; i++){
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,1);
if(ok)break;
}
if(ok)cout<<1;
else cout<<0;
}문제를 풀면서 배열을 초기화 할때 A[n][n]으로 만들어서 모든 수를 -1 로 넣고 -1일때 컨티뉴로 넘기는 식으로 했다가 시간 초과가 발생하여 A[i]의 길이를 인자값 받는 만큼으로 변경하여 통과하였습니다.
