fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define M 1000000007
  4. #define F first
  5. #define S second
  6. #define mp make_pair
  7. #define pb push_back
  8. #define gcd __gcd
  9. #define in(a) scanf("%d",&a)
  10. #define in2(a,b) scanf("%d%d",&a,&b)
  11. #define in3(a,b,c) scanf("%d%d%d",&a,&b,&c)
  12. #define sc(ch) scanf("%c",&ch)
  13. #define sstr(str) scanf("%s",str)
  14. #define pr(n) printf("%d ",n)
  15. #define out(n) printf("%d\n",n)
  16. #define cf(n) printf("%I64d\n",n)
  17. #define yes printf("YES\n")
  18. #define no printf("NO\n")
  19. #define lin printf("\n")
  20. #define dbg(v,n) for(i=0;i<n;i++)pr(v[i]); lin
  21. #define ck printf("continue\n")
  22. #define ii pair<int,int>
  23. #define vi vector<int>
  24. #define vii vector<pair<int,int> >
  25. #define vvi vector<vector<int> >
  26. #define viii vector<pair<pair<int,int>,int> >
  27. #define vvii vector<vector<pair<int,int> > >
  28. #define st(vec) sort(vec.begin(),vec.end())
  29. #define lp(i,a,b) for(i=a;i<b;i++)
  30. typedef long long int ll;
  31. #define N 50005
  32. vvi ad(N);
  33. bool vis[N];
  34. bitset<N> sub[N];
  35. void dfs(int s)
  36. {
  37.     int i,x,a,j;
  38.     vis[s]=1;
  39.     x=ad[s].size();
  40.     sort(ad[s].begin(),ad[s].end());
  41.     i=0;
  42.     while(i<x)
  43.     {
  44.         j=i;
  45.         while(j+1<x & ad[s][j]==ad[s][j+1])
  46.             j++;
  47.         i=j+1;
  48.         a=ad[s][j];
  49.         if(!vis[a])
  50.             dfs(a);
  51.         sub[s]|=sub[a];
  52.     }
  53.     sub[s].set(s);
  54.     return ;
  55. }
  56. int main()
  57. {
  58.     int n,m,i,a,b;
  59.     in2(n,m);
  60.     while(m--)
  61.     {
  62.         in2(a,b);
  63.         ad[a-1].pb(b-1);
  64.     }
  65.     for(i=0;i<n;i++)
  66.     {
  67.         if(!vis[i])
  68.             dfs(i);
  69.     }
  70.     a=0;
  71.     for(i=0;i<n;i++)
  72.         if(2*sub[i].count()>=n)a++;
  73.     out(a);
  74.  
  75.  
  76. }
Success #stdin #stdout 0s 320768KB
comments (?)
stdin
copy 
5 4
1 2
3 2
2 4
4 5
stdout
copy 
3
https://ideone.com/pPFsz8
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

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!