개발자 톡

연습문제 톡 [HSAT 6회 정기 코딩 인증평가 기출] 출퇴근길

32번 테스트 케이스 부터 계속 오답이 납니다 . 예외나 문제점 알려주시면 감사하겠습니다.

등록일
2024-11-08 17:21:39
조회수
97
작성자
sdfg8931

#include<iostream>

#include<algorithm>

#include<vector>

// #define DEBUG

using namespace std;



bool visit_list[200001];

bool is_sroop_list[200001]={0,};

bool is_troop_list[200001]={0,};

int order_list[200001];

vector<int> edge_list[200001];

int order =0;



bool dfs(int current , bool* is_roop_list){

#ifdef DEBUG

cout << "order : "<< order_list[current] << " current : "<< current << endl;

cout << "order list : ";

for (int i=0; i<10; i++){

cout << order_list[i]<< " ";

}

cout << endl;


#endif


if(order_list[current] ==0){

order++;

order_list[current] = order;

}




for(int node: edge_list[current]){

#ifdef DEBUG

cout << " current child node : "<< node << endl;

#endif


if( is_roop_list[node]){


is_roop_list[current] = true;


}


else if(!visit_list[node]){


visit_list[node]=true;

is_roop_list[current] = (is_roop_list[current] | dfs(node, is_roop_list));

visit_list[node]=false;



}

else if(order_list[current]> order_list[node]){

is_roop_list[current] = (is_roop_list[current] | dfs(node, is_roop_list));

// visit_list[node]=false;



}

}


#ifdef DEBUG

cout << "current "<< current <<"return is roop : " << is_roop_list[current]<<endl;

#endif


return is_roop_list[current];

}


int main(){

int N, M;

cin >> N >> M;


for(int i= 0; i<M; i++){


int start ,end;

cin >> start >> end;

edge_list[start].push_back(end);


}


int S, T;

cin >> S >> T;


order=1;


for(int i=0; i<200001; i++){

order_list[i]=0;

visit_list[i]=0;

is_sroop_list[i]=0;

}

order_list[S]=1;

is_sroop_list[S] =true;

is_sroop_list[T] =true;

dfs(S, is_sroop_list );


#ifdef DEBUG

cout <<"first dfs============="<<endl;

#endif




#ifdef DEBUG

cout <<"second dfs============="<<endl;

#endif


for(int i=0; i<200001; i++){

order_list[i]=0;

visit_list[i]=0;

is_troop_list[i]=0;

}

order=1;

is_troop_list[T]=true;

is_troop_list[S]=true;

order_list[T]=1;

dfs(T ,is_troop_list );




int result =0;


for(int i=0; i<200001; i++){

result += (is_sroop_list[i]&is_troop_list[i]);

}


#ifdef DEBUG


for(int i=0; i<20; i++){

cout<< is_sroop_list[i] << " ";

}

cout << endl;

for(int i=0; i<20; i++){

cout<< is_troop_list[i] << " ";

}


#endif


cout << max(result-2,0);



}

#[HSAT_6회_정기_코딩_인증평가_기출]_출퇴근길

이 카테고리의 톡 더보기