Sicily 1034-蒲公英云

Sicily 1034

蔚落 2022-08-06 07:09 125阅读 0赞

#include
#include
using namespace std;
int invalid_flag;
struct node{
int m; //记录指向该节点的节点
int n; //记录该节点的层次
};
int main()
{
int a,b;
while(cin>>a>>b)
{
if(a==0)
break;
invalid_flag=0;
int num[100][100]; //记录树的边
int root[100]; //root存放根节点，值为1表示是根节点
int level[100]; //记录第i个节点的层数
int width[100]; //记录第i层的宽度
queue q;
for(int i=0;i<a;i++)
{
root[i]=1;
level[i]=-1;
}
for(int i=0;i<a;i++)
for(int j=0;j<a;j++)
num[i][j]=0;

 for(int i=0;i<b;i++)  
\{  
    int c=0,d=0;  
    cin>>c>>d;  
    c--;d--;  
    root\[d\]=0;                       //判断是否为根节点  
    num\[c\]\[d\]=1;  
\}     
for(int i=0;i<a;i++)                 //从根节点入队列，依次遍历  
    if(root\[i\]==1)  
    \{  
        level\[i\]=0;

node temp={i,0};
q.push(temp);
}

while(!q.empty())

{
node temp1=q.front(); //取出队列首个元素
q.pop();
for(int i=0;i<a;i++)
{
if(num[temp1.m][i]==1)
{
if(level[i]!=-1)
{
invalid_flag=1;
break;
}
else
{
level[i]=temp1.n+1;
node temp2={i,level[i]};
q.push(temp2);
}
}
}

if(invalid_flag==1)
break;
}

for(int i=0;i<a;i++)      //判断是否有节点未被访问  
 if(level\[i\]==-1)  
\{  
  invalid\_flag=1;  
  break;  
   \}

if(invalid_flag==1)
cout<<”INVALID”<<endl;
else
{
int max_e1=0;
int max_e2=0;
for(int i=0;i<a;i++)
width[i]=0;

for(int i=0;i<a;i++)         //求最深层数  
 \{  
    if(level\[i\]>max\_e1)  
    max\_e1=level\[i\];  
    width\[level\[i\]\]++;        //得出第i层的宽度  
 \}  
for(int i=0;i<a;i++)           //求最宽节点数  
 \{  
    if(width\[i\]>max\_e2)  
    max\_e2=width\[i\];  
 \}  
 cout<<max\_e1<<" "<<max\_e2<<endl;