Advertisement
Saleh127

Light OJ 1111 / BFS

Nov 19th, 2021
837
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-19-22.43.39
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11. vector<ll>g[20005];
  12. bool v[20005];
  13. ll cnt[20005];
  14.  
  15. void bfs(ll u)
  16. {
  17.      memset(v,0,sizeof v);
  18.  
  19.      queue<ll>q;
  20.      q.push(u);
  21.      cnt[u]++;
  22.      v[u]=1;
  23.  
  24.      while(q.empty()==false)
  25.      {
  26.           ll x=q.front();
  27.           q.pop();
  28.  
  29.           for(auto d:g[x])
  30.           {
  31.                if(v[d]==0)
  32.                {
  33.                     q.push(d);
  34.                     cnt[d]++;
  35.                     v[d]=1;
  36.                }
  37.           }
  38.      }
  39.  
  40.      return;
  41. }
  42.  
  43. int main()
  44. {
  45.    ios_base::sync_with_stdio(0);
  46.    cin.tie(0);cout.tie(0);
  47.  
  48.    test
  49.    {
  50.         ll n,m,i,j,k,l,ans=0;
  51.  
  52.         cin>>k>>n>>m;
  53.  
  54.         ll a[n+4];
  55.  
  56.         for(i=0;i<k;i++) cin>>a[i];
  57.  
  58.         for(i=0;i<m;i++)
  59.         {
  60.              cin>>j>>l;
  61.  
  62.              g[j].push_back(l);
  63.         }
  64.  
  65.         for(i=0;i<k;i++)
  66.         {
  67.              bfs(a[i]);
  68.         }
  69.  
  70.         for(i=1;i<=n;i++)
  71.         {
  72.              if(cnt[i]==k) ans++;
  73.         }
  74.  
  75.         cout<<"Case "<<cs<<": "<<ans<<nl;
  76.  
  77.         for(i=0;i<=10009;i++)
  78.         {
  79.              g[i].clear();
  80.              v[i]=0;
  81.              cnt[i]=0;
  82.         }
  83.  
  84.    }
  85.  
  86.    get_lost_idiot;
  87. }
  88.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement