fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #define maxn 10001
  6. using namespace std;
  7. vector<int> G[maxn];
  8. int BeFok[maxn];
  9. int van_szulo[maxn],van_gyerek[maxn],szulo[maxn][2];
  10. int n;
  11.  
  12. // mintafeladat megoldását használva
  13. // él: gyerek felé mutat
  14. void Beolvas(){
  15.    int m,p,q1,q2;
  16.    cin>>n>>m;
  17.    for(int i=1;i<=n;i++){BeFok[i]=0;van_szulo[i]=0;van_gyerek[i]=0;}
  18.    for (int i=0;i<m;i++){
  19.       cin>>p>>q1>>q2;
  20.       G[q1].push_back(p);
  21.       G[q2].push_back(p);
  22.       BeFok[p]+=2;
  23.       szulo[p][0]=q1;
  24.       szulo[p][1]=q2;
  25.       van_szulo[p]=1;
  26.       van_gyerek[q1]=1;
  27.       van_gyerek[q2]=1;
  28.    }
  29. }
  30.  
  31. int main(){
  32.    Beolvas();
  33.    vector<int> nev[n];
  34.    int cnt,d,i,j,p,q,si,si2,size,szulo1,szulo2,melyseg=0,sol[maxn];
  35.    unsigned int bit[32],**os,ans[maxn+1];
  36.  
  37.    // topologikus sorrend megkeresése
  38.    for (int p=1;p<=n;p++)
  39.       if(BeFok[p]==0)
  40.          nev[0].push_back(p);
  41.  
  42.    while(nev[melyseg].size()>0){
  43.      si=nev[melyseg].size(); 
  44.      for(i=0;i<si;i++){
  45.          p=nev[melyseg][i];
  46. 	 si2=G[p].size();
  47. 	 for(j=0;j<si2;j++){
  48. 	    q=G[p][j];
  49.             BeFok[q]--;
  50.             if(BeFok[q]==0)
  51.                nev[melyseg+1].push_back(q);
  52.          }
  53.       }
  54.       melyseg++;
  55.    }
  56.  
  57.    bit[0]=1;for(i=1;i<32;i++)bit[i]=2*bit[i-1];
  58.  
  59.    si=(n+32)/32;
  60.    os=(unsigned int**)malloc((n+1)*sizeof(unsigned int*));
  61.    for(i=0;i<=n;i++)os[i]=(unsigned int*)malloc(si*sizeof(unsigned int));
  62.  
  63.    // Mindenkinek megkeresem az őseit, topologikus sorrendben veszem a pontokat, így egy pontra ez csak O(n) időbe kerül
  64.    // igazából máshogy is O(n) idő lenne, de pont a top. sorrend miatt a szülők ősei ismertek, így lehet "éselni", azaz gyorsítani
  65.    // az egész algoritmust!
  66.    for(d=0;d<melyseg;d++){
  67.        size=nev[d].size();
  68.        for(i=0;i<size;i++){
  69. 	   p=nev[d][i];
  70. 	   if(!van_szulo[p]){for(j=0;j<si;j++)os[p][j]=0;}
  71. 	   else{
  72. 	     szulo1=szulo[p][0];
  73. 	     szulo2=szulo[p][1];
  74. 	     for(j=0;j<si;j++)os[p][j]=os[szulo1][j]|os[szulo2][j];
  75. 	     os[p][szulo1>>5]|=bit[szulo1&31];
  76. 	     os[p][szulo2>>5]|=bit[szulo2&31];
  77. 	   }
  78.        }
  79.    }
  80.  
  81.    for(j=0;j<si;j++)ans[j]=0xffffffff;
  82.    for(d=0;d<melyseg;d++){
  83.       size=nev[d].size();
  84.       for(i=0;i<size;i++){
  85.          p=nev[d][i];
  86.          if(!van_gyerek[p])
  87. 	   {for(j=0;j<si;j++)ans[j]&=os[p][j];}// nincs gyereke p-nek
  88.       }
  89.    }
  90.  
  91.    cnt=0;
  92.    for(i=1;i<=n;i++)
  93.        if(ans[i>>5]&bit[i&31])sol[cnt++]=i;// az "i" közös ős lesz
  94.  
  95.   cout<<cnt<<endl;
  96.   if(cnt){
  97.     for(i=0;i<cnt;i++){cout<<sol[i];if(i<cnt-1)cout<<" ";}
  98.     cout<<endl;
  99.   }
  100.  
  101.   return 0;
  102. }
  103.  
Success #stdin #stdout 0s 3776KB
comments (?)
stdin
copy 
20 13 
4 3 8
5 8 9
6 11 12
7 13 15
3 1 16
8 2 17
9 16 10
11 16 10
12 17 10
13 16 14
15 17 14
16 18 19
17 19 20
stdout
copy 
5
16 17 18 19 20
https://ideone.com/QWOfvU
language:
C++ (gcc 8.3)
created:
8 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!