개발자 톡
32번 테스트 케이스 부터 계속 오답이 납니다 . 예외나 문제점 알려주시면 감사하겠습니다.
- 등록일
- 2024-11-08 17:21:39
- 조회수
- 62
- 작성자
- 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);
}