1034. Forest

TAG 数据结构 树 树的深度 宽度

虽然是水题，情况没处理好，还wa了几次，囧。

#include <stdio.h>
#include <memory.h>
const int N=100;
bool map[N][N];
bool multiedge;
bool invalid;
int  wid[N];
int  depth,width;
int n,m,a,b;
bool visited[N];
bool indegree[N];
void tra(int d, int p)
{
	if ( d>depth )
	{
		depth=d;
	}
	for (int i=0; i<n && !invalid; ++i)
	{
		if ( map[p][i] )
		{
			if ( visited[i] )
			{
				invalid=true;
				return;
			}
			visited[i]=true;
			++wid[d+1];
			tra(d+1, i);
		}
	}
}
bool cal()
{
	depth=width=0;
	memset(visited, false, sizeof(visited) );
	memset(wid, 0, sizeof(wid) );
 
	for (int i=0; i<n; ++i)
	{
		if ( !indegree[i] )
		{
			++wid[0];
			visited[i]=true;
			tra(0,i);
		}
	}
    //如果有节点没访问到，就说明有loop，比如3个节点3条边连成一个loop的情况
	for (int i=0; i<n; ++i) 
	{
        if ( !visited[i] ) 
        {
             invalid=true;
             break;
        }
    }
	for (int i=0; i<=depth; ++i)
	{
		if (width<wid[i] )
		{
			width=wid[i];
		}
	}
}
int main(int argc, char *argv[])
{
	while ( scanf("%d%d", &n, &m) && n!=0 )
	{
		multiedge=false;
		memset(map, false, sizeof(map) );
		memset(indegree, false, sizeof(indegree) );
		for (int i=0; i<m; ++i)
		{
			scanf("%d%d",&a, &b);
			map[a-1][b-1]=true;
            
			if ( indegree[b-1] )
			{
				multiedge=true;
			}
			indegree[b-1]=true; 
		}
		invalid=false;
		if ( multiedge  )
		{
			printf("INVALID/n");
		}
		else
		{
			cal(); //在计算的时候顺便判断loop
			if ( invalid )
			{
				printf("INVALID/n");
			}
			else 
			{
				printf("%d %d/n",depth, width);
			}
		}
	}
	return 0;
}