Sicily 1034

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

\#include<iostream>  
\#include <queue>  
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<node> 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;   
 \}   
\}  
return 0;  
\}

1.对于跳出双重循环，本来打算用goto，但最后还是想到了妥善的解决办法

2.SIcily中提交结果说明：

![Image 1][]

[Image 1]: