Pagini recente » Cod sursa (job #85425) | Cod sursa (job #1830345) | Cod sursa (job #572790) | Cod sursa (job #721809) | Cod sursa (job #890779)
Cod sursa(job #890779)
#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;
}