BOJ 26146 - 즉흥 여행 (Easy)

BOJ 26146 - 즉흥 여행 (Easy)

SCC를 찾아 그것의 개수가 1이라면 정답은 Yes이다.

SCC를 쓰지 않고, 어떤 정점 $u$에서 정방향 간선으로 DFS를 돌려 모두 도달할 수 있고, 역방향 간선으로 DFS를 돌려 모두 도달할 수 있다면 Yes 라는 것으로 풀 수도 있다.

struct SCC {  
   int N, dfsn = 0, size = 0;  
   vi fin, order, t;  
   vvi edges;  
   SCC(int N) : N(N) {  
      fin = vi(N);  
      order = vi(N, -1);  
      edges = vvi(N);  
   }  
  
   void add_edge(int u, int v) {  
      edges[u].pb(v);  
   }  
  
   void find() {  
      for (int i = 0; i < N; i++) {  
         if (!fin[i]) {  
            dfs(i);  
         }  
      }  
   }  
  
   int dfs(int i) {  
      t.pb(i);  
      order[i] = dfsn++;  
      int ret = order[i];  
  
      for (int to: edges[i]) {  
         if (!fin[to]) {  
            if (order[to] == -1) ret = min(ret, dfs(to));  
            else ret = min(ret, order[to]);  
         }  
      }  
  
      if (order[i] == ret) {  
         while (1) {  
            int top = t.back();  
            fin[top] = 1;  
            t.pop_back();  
            if (top == i) break;  
         }  
         size++;  
         if (size == 2) {  
            cout << "No";  
            exit(0);  
         }  
      }  
      return ret;  
   }  
};  
// endregion  
  
  
  
void solve() {  
   struct stat st;  
   fstat(0, &st);  
   char *p = (char *) mmap(0, st.st_size, PROT_READ, MAP_SHARED, 0, 0);  
   auto readInt = [&]() {  
      int ret = 0;  
      for (char c = *p++; c & 16; ret = 10 * ret + (c & 15), c = *p++);  
      return ret;  
   };  
   int n = readInt(), m = readInt();  
   SCC scc(n);  
   for (int i = 0, u, v; i < m; i++) {  
      u = readInt() - 1, v = readInt() - 1;  
      scc.add_edge(u, v);  
   }  
   scc.find();  
   cout << (scc.size == 1 ? "Yes" : "No");  
}