fork download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3.  
  4.  
  5. using namespace std;
  6. using ii = pair < int , int >;
  7.  
  8. const int N   = 5e5 + 5;
  9. const int INF = 2e9;
  10.  
  11.  
  12. int n , m;
  13.  
  14. vector < int > adj[N];
  15.  
  16. int SCC_Size[N]; // size of the largest SCC the node (i) belongs to
  17.  
  18. int low[N] , dfn[N] , timer = 0;
  19. vector < int > nodesStack;
  20. bool inStack[N];
  21.  
  22. void dfs(int u) {
  23.     dfn[u] = low[u] = ++ timer;
  24.     nodesStack.push_back(u);
  25.     inStack[u] = 1;
  26.  
  27.     for(int v : adj[u]) {
  28.             if(!dfn[v]) {
  29.                     dfs(v);
  30.             }
  31.  
  32.             if(inStack[v]) {
  33.                     low[u] = min(low[u] , low[v]);
  34.             }
  35.     }
  36.  
  37.     if(low[u] == dfn[u]) {
  38.  
  39.             int sz = 0;
  40.             vector < int > tmp;
  41.  
  42.             while(true) {
  43.                     int v = nodesStack.back(); nodesStack.pop_back(); inStack[v] = 0;
  44.  
  45.                     sz ++;
  46.                     tmp.push_back(v);
  47.  
  48.                     if(v == u) break;
  49.             }
  50.  
  51.             for(int T : tmp) {
  52.                     SCC_Size[T] = sz;
  53.             }
  54.     }
  55. }
  56.  
  57.  
  58. void solve(){
  59.  
  60.     int k;
  61.     scanf("%d %d %d" , &n , &m , &k);
  62.  
  63.     for(int i = 0 ; i < m ; i ++){
  64.  
  65.         int u , v;
  66.         scanf("%d %d" , &u , &v);
  67.         adj[u].push_back(v);
  68.     }
  69.  
  70.     for(int i = 1 ; i <= n ; i ++) {
  71.             if(!dfn[i]) {
  72.                     dfs(i);
  73.             }
  74.     }
  75.  
  76.     int q; scanf("%d" , &q);
  77.  
  78.     while( q -- ){
  79.             int x; scanf("%d" , &x);
  80.  
  81.             if(SCC_Size[x] >= k) {
  82.                     printf("Yes\n");
  83.             }
  84.             else {
  85.                     printf("No\n");
  86.             }
  87.     }
  88.  
  89. }
  90.  
  91.  
  92. main(){
  93.     solve();
  94.     return 0;
  95. }
  96.  
  97.  
Success #stdin #stdout 0s 15316KB
comments (?)
stdin
copy 
 5 4 2
 1 2
 2 3
 3 1
 4 5
 3
 1
 4
 2
stdout
copy 
Yes
No
Yes
https://ideone.com/1La49a
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!