소프티어

반례를 너무 못 찾겠어서 구글링했습니다.

근데 구글에서는 dfs를 네 번 돌리더라구요.

S출발, T출발 뿐만 아니라 역방향 그래프를 만들어서 S까지 갈 수 있는 노드, T까지 갈 수 있는 노드를 구하기 위해서요..

도대체 왜죠...? 상황은 이해 돼서 적절한 반례를 여러 가지 해 봤는데 답이 똑같이 나와요 구글 코드와 ...

6 10

1 2 

2 6

3 1

1 4

4 1

4 5

5 4

5 6 

6 5

6 3

1 6

(시도했던 반례입니다)

다른 반례를 찾을 수 있는 고수를 찾습니다..

반례를 안 찾더라도 왜 역방향 그래프를 만들어서 dfs를 두 번 더 돌려야 하는지 설명해 주시면 감사하겠습니다..

#include<iostream>

#include <queue>

#include <algorithm>

#include <cstring>

#include <vector>

using namespace std;

vector<vector<int>> map;

bool visited[100001];

vector<int> StoT;

vector<int> TtoS;

vector<int> bfs(int start, int end){

  vector<int> order;

  queue<int> q;

  q.push(start);

  //visited[start] = true;

  while(!q.empty()){

    int cur = q.front();

    q.pop();

    for (auto& n: map[cur]){

      if(visited[n] || n == end) continue;

      if (map[n].size() == 0) continue;

      if (n != start)

        {visited[n] = true;

      order.push_back(n);}

      q.push(n);

    }

  }

  /*for (auto& n: order)

    cout << n<< ' ';

  cout << '\n';*/

  return order;

}

int main(int argc, char** argv)

{

  ios::sync_with_stdio(false);

  cin.tie(nullptr);

  int n, m, s, t ,cnt = 0;

  cin >> n >> m;

  map.resize(n+1);

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

    int x, y;

    cin >> x >> y;

    map[x].push_back(y);

  }

  cin >> s >> t;

  //cout << "StoT\n";

  StoT = bfs(s, t);

  memset(visited, 0, sizeof(visited));

  //cout << "TtoS\n";

  TtoS = bfs(t, s);

  sort(StoT.begin(), StoT.end());

  sort(TtoS.begin(), TtoS.end());

  while(!StoT.empty()){

    int cur = StoT.front();

    StoT.erase(StoT.begin());

    int idx = 0;

    while(idx < TtoS.size() && TtoS[idx] != cur) idx++;

    if(idx < TtoS.size()){ // 찾았으면

      //cout << "find: " << TtoS[idx] << '\n';

      TtoS.erase(TtoS.begin() + idx);

      cnt++;

    }

  }

  cout << cnt;

  return 0;

}