Cod sursa(job #890779)

Utilizator starduststardust stardust Data 25 februarie 2013 11:49:40
Problema Amenzi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
#include <cstring>
#define maxn 16100


using namespace std;
ifstream in("color2.in");
ofstream out("color2.out");
int tata[maxn];
int fiu[maxn][2];
int n;
int sus[maxn],jos[maxn];
void read()
{
    in>>n;
    int x,y;
    for(int i=1;i<n;i++)
    {
        in>>x>>y;
        tata[y]=x;
        if(fiu[x][0]==0) fiu[x][0]=y;
        else fiu[x][1]=y;
    }
}

int memojos(int nod)
{
    if(jos[nod]!=-1) return jos[nod];
    if(fiu[nod][0]!=0)
      {
          if(memojos(fiu[nod][0])+memojos(fiu[nod][1])==0) jos[nod]=1;
          else jos[nod]=0;
      }
    else jos[nod]=1;
    return jos[nod];
}

int memosus(int nod)
{
    int frate;
    if(fiu[tata[nod]][0]==nod) frate=fiu[tata[nod]][1];
    else frate=fiu[tata[nod]][0];

    if(sus[nod]!=-1) return sus[nod];
    if(tata[nod]!=0)
    {
        if(memosus(tata[nod])==0 || memojos(frate)==1) sus[nod]=1;
        else sus [nod]=0;
    }
    else sus[nod]=1;
    return sus[nod];

}

int main()
{
    read();
    int cnt=0;
    memset(sus,-1,sizeof(sus));
    memset(jos,-1,sizeof(jos));
    //memojos(1);
    for(int i=1;i<=n;i++)
       memosus(i),memojos(i);
    for(int i=1;i<=n;i++)
     if(sus[i]==1 && jos[i]==1) cnt++;

     out<<cnt<<"\n";
     for(int i=1;i<=n;i++)
     if(sus[i]==1 && jos[i]==1) out<<i<<" ";
    return 0;
}