Submission #1688508

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;
 
const int MAX = 200010;
int N, M;
bool visit0[MAX], visitN[MAX];
 
vector<int> graph[MAX];
 
void dfs1(int n) {
  if (visit0[n]) return;
  
  visit0[n] = true;
  for (int i = 0; i < graph[0].size(); i++) {
    dfs1(graph[0][i]);
  }
}
 
void dfs2(int n) {
  if (visitN[n]) return;
  
  visitN[n] = true;
  for (int i = 0; i < graph[N-1].size(); i++) {
    dfs2(graph[N-1][i]);
  }
}
 
int main(int argc, const char * argv[]) {
  cin >> N >> M;
  int a[M], b[M];
  for (int i = 0; i < M; i++) {
    cin >> a[i] >> b[i];
    a[i]--; b[i]--;
    graph[a[i]].push_back(b[i]);
    graph[b[i]].push_back(a[i]);
  }
  
  dfs1(0);
  dfs2(N-1);
  
  bool flag = false;
  for (int i = 0; i < N; i++) {
    if (visit0[i] && visitN[i]) flag = true;
  }
  
  // 解答
  cout << (flag ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    
  return 0;
}

Submission Info

Judge Result