fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #define maxn 10001
  7. using namespace std;
  8. vector<int> G[maxn];
  9. int BeFok[maxn];
  10. int van_szulo[maxn],van_gyerek[maxn],szulo[maxn][2];
  11. int n;
  12.  
  13. // mintafeladat megoldását használva
  14. // él: gyerek felé mutat
  15. void Beolvas(){
  16.    int m,p,q1,q2;
  17.    scanf("%d%d",&n,&m);
  18.    for(int i=1;i<=n;i++){BeFok[i]=0;van_szulo[i]=0;van_gyerek[i]=0;}
  19.    for (int i=0;i<m;i++){
  20.       scanf("%d%d%d",&p,&q1,&q2);
  21.       G[q1].push_back(p);
  22.       G[q2].push_back(p);
  23.       BeFok[p]+=2;
  24.       szulo[p][0]=q1;
  25.       szulo[p][1]=q2;
  26.       van_szulo[p]=1;
  27.       van_gyerek[q1]=1;
  28.       van_gyerek[q2]=1;
  29.    }
  30. }
  31.  
  32. int main(){
  33.    Beolvas();
  34.    vector<int> nev[n];
  35.    int cnt,d,i,j,p,q,si,si0,si1,si2,size,szulo1,szulo2,pos,pos1,pos2,melyseg=0,inv[maxn+1],sol[maxn],meret[maxn+1];
  36.    unsigned int bit[32],**os,ans[maxn+1];
  37.  
  38.    // topologikus sorrend megkeresése
  39.    for (int p=1;p<=n;p++)
  40.       if(BeFok[p]==0)
  41.          nev[0].push_back(p);
  42.  
  43.    while(nev[melyseg].size()>0){
  44.      si=nev[melyseg].size(); 
  45.      for(i=0;i<si;i++){
  46.          p=nev[melyseg][i];
  47. 	 si2=G[p].size();
  48. 	 for(j=0;j<si2;j++){
  49. 	    q=G[p][j];
  50.             BeFok[q]--;
  51.             if(BeFok[q]==0)
  52.                nev[melyseg+1].push_back(q);
  53.          }
  54.       }
  55.       melyseg++;
  56.    }
  57.  
  58.    bit[0]=1;for(i=1;i<32;i++)bit[i]=2*bit[i-1];
  59.  
  60.    si=(n+32)/32;
  61.    os=(unsigned int**)malloc((n+1)*sizeof(unsigned int*));
  62.    //for(i=0;i<=n;i++)os[i]=(unsigned int*)malloc(si*sizeof(unsigned int));
  63.  
  64.    pos=1;
  65.    int elso=n+1;// top. sorrend szerinti első gyerektelen
  66.                 // triviálsian ettől balra lehetnek csak a gyerektelenek közös ősei
  67.  
  68.    // Mindenkinek megkeresem az őseit, topologikus sorrendben veszem a pontokat, így egy pontra ez csak O(n) időbe kerül
  69.    // igazából máshogy is O(n) idő lenne, de pont a top. sorrend miatt a szülők ősei ismertek, így lehet "vagyolni", azaz gyorsítani
  70.    // az egész algoritmust!
  71.    for(d=0;d<melyseg;d++){
  72.        size=nev[d].size();
  73.        for(i=0;i<size;i++){
  74. 	   p=nev[d][i];
  75. 	   inv[p]=pos;
  76. 	   if(van_gyerek[p]==0&&elso==n+1)elso=pos;
  77.  
  78. 	   if(!van_szulo[p]){meret[pos]=0;}
  79. 	   else{
  80. 	     szulo1=szulo[p][0];pos1=inv[szulo1];si1=meret[pos1];
  81. 	     szulo2=szulo[p][1];pos2=inv[szulo2];si2=meret[pos2];
  82. 	     if(si1>si2){swap(pos1,pos2);swap(si1,si2);}
  83.  
  84. 	     si0=max(si1,si2);
  85. 	     if(pos1<elso)si0=max(si0,pos1);
  86. 	     if(pos2<elso)si0=max(si0,pos2);
  87. 	     meret[pos]=si0;
  88. 	     si=(si0+32)/32;
  89. 	     os[pos]=(unsigned int*)malloc(si*sizeof(unsigned int));
  90.  
  91. 	     si1=(si1+31+(si1>0))/32;si2=(si2+31+(si2>0))/32;
  92.  
  93. 	     for(j=0;j<si1;j++)os[pos][j]=os[pos1][j]|os[pos2][j];
  94. 	     for(j=si1;j<si2;j++)os[pos][j]=os[pos2][j];
  95. 	     for(j=si2;j<si;j++)os[pos][j]=0;
  96. 	     if(pos1<elso)os[pos][pos1>>5]|=bit[pos1&31];
  97. 	     if(pos2<elso)os[pos][pos2>>5]|=bit[pos2&31];
  98. 	   }
  99. 	   pos++;
  100.        }
  101.    }
  102.  
  103.    si=(elso+31)/32;
  104.    for(j=0;j<si;j++)ans[j]=0xffffffff;
  105.    for(d=0;d<melyseg;d++){
  106.       size=nev[d].size();
  107.       for(i=0;i<size;i++){
  108.          p=nev[d][i];
  109.          if(!van_gyerek[p])
  110. 	   {pos=inv[p];
  111. 	     si2=meret[pos];
  112. 	     si2=(si2+31+(si2>0))/32;
  113. 	     for(j=0;j<si2;j++)ans[j]&=os[pos][j];}// nincs gyereke p-nek
  114.       }
  115.    }
  116.  
  117.    cnt=0;
  118.    for(i=1;i<=n;i++){
  119.        pos=inv[i];
  120.        if(pos<elso&&(ans[pos>>5]&bit[pos&31]))sol[cnt++]=i;// az "i" közös ős lesz
  121.    }
  122.  
  123.   printf("%d\n",cnt);
  124.   if(cnt){
  125.     for(i=0;i<cnt;i++){printf("%d",sol[i]);if(i<cnt-1)printf(" ");}
  126.     printf("\n");
  127.   }
  128.  
  129.   return 0;
  130. }
  131.  
Success #stdin #stdout 0s 3812KB
comments (?)
stdin 
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 
5
16 17 18 19 20
https://ideone.com/GCdW8k
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!