学步园

看了BBS上的题目分类说要DFS，但是听了舍友的建议，发现用一位数组存貌似也比较方便，所以就用了一位数组存。这个一位数组的元素是一个结构体，包括三个元素，fa、level、in分别表示父节点下标、当前节点层数、当前节点入度数。

首先要先考虑特殊情况，这一点其实样例中已经给出了，就是当m=0的时候，森林的深度为0，而其宽度为结点个数（因为都是根节点，我本来YY m=0时只会输出0 1...结果...）。读入时更新fa和in，当in>=2时用flg记录下来，表示已经出现“two edges pointing to the same node”。接下来要判断是否有环，这里是从当前结点往前推看是否能退出其自身就是自己的祖先，如果可以自然有环，其次，若已经向上退了n的结点还没有出现结点0或者前一种情况，则说明，有环使循环陷入死循环了。判断完了非法状态，现在就要计算森林深度和宽度，根据每个结点的fa项可以比较方便的推出（邻接矩阵貌似就比较麻烦处理了，但是前面非法状态的判断会容易些），再遍历每个节点，根据其所在的层更新width[]数组（该数组记录第i层上的元素），则所求即为max(width[i])，至此解决问题。

附上代码：

#include <iostream><br /> #include <cstring><br /> using namespace std;<br /> struct node<br /> {<br /> int fa,level,in;<br /> node()<br /> {<br /> fa=in=0;<br /> level=-1;<br /> }<br /> };<br /> int main()<br /> {<br /> int n,m;<br /> while (cin>>n>>m && n)<br /> {<br /> if (m==0)//特殊情况处理<br /> {<br /> cout<<"0 "<<n<<endl;<br /> continue;<br /> }<br /> node f[n+1];<br /> int flg=true;<br /> for (int i=1;i<=m;i++)//数据读入<br /> {<br /> int x,y;<br /> cin>>x>>y;<br /> f[y].fa=x;<br /> f[y].in++;<br /> if (f[y].in>=2) flg=false;<br /> }<br /> for (int i=1;i<=n;i++)//判断是否有环<br /> {<br /> int t=f[i].fa,k=1;<br /> while (t!=0 && t!=i && k<=n)<br /> {<br /> k++;<br /> t=f[t].fa;<br /> }<br /> if (t==i || k>n)<br /> {<br /> flg=false;<br /> break;<br /> }<br /> }<br /> if (!flg)//如果有环或者有入读为2的结点则结束<br /> {<br /> cout<<"INVALID"<<endl;<br /> continue;<br /> }<br /> int mdep,count=0;<br /> for (int i=1;i<=n;i++)//更新所有树的根节点的层数，即0<br /> if (f[i].fa==0)<br /> {<br /> f[i].level=0;<br /> count++;<br /> }<br /> mdep=0;<br /> while (count!=n)//更新除根节点以外的结点的层数<br /> {<br /> mdep++;<br /> for (int i=1;i<=n;i++)<br /> if (f[f[i].fa].level==mdep-1)<br /> {<br /> f[i].level=mdep;<br /> count++;<br /> }<br /> }<br /> cout<<mdep<<" ";<br /> int mwid=0,width[mdep+1];<br /> memset(width,0,sizeof(width));<br /> for (int i=1;i<=n;i++)//由结点的层数推得每层的结点数存在width[]中，则森林的宽度即为max(width[i])<br /> {<br /> width[f[i].level]++;<br /> mwid=mwid<width[f[i].level]?width[f[i].level]:mwid;<br /> }<br /> cout<<mwid<<endl;<br /> }<br /> return 0;<br /> }<br />