本文主要是介绍1034 forest，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
大水题，WA到吐了，结果发现犯了一弱智错误，擦
1.定义dept[]数组，主要用bfs ,将子节点的dept值累加父节点的dept值,遍历一颗或者若干树。从根节点（bepointed[]值为false的点）出发遍历全棵树。
2.存储方式：邻接表存边 vector+queue ,
#include <iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;int n,m,a,b;
const int N=102;
bool bepointed[N];
bool circle[N];
int dept[N];
bool flag;
vector<int>vec[N];bool cmp(const int&a,const int &b)
{return a>b;
}void bfs(int vertex)
{queue<int>que1;que1.push(vertex);while (!que1.empty()){int a=que1.front();circle[a]=true;que1.pop();for (int i=0;i<vec[a].size();i++){int j=vec[a][i];if(circle[j]==false){dept[j]=dept[a]+1;que1.push(j);} }}
}int main()
{while(cin>>n>>m&&n!=0){flag=0;memset(bepointed,false,sizeof(bepointed));memset(circle,false,sizeof(circle));memset(dept,0,sizeof(dept));fill(vec,vec+n+1,vector<int>());while (m--){cin>>a>>b;if(bepointed[b]==true) flag=1; //terrible mistake i've madebepointed[b]=true; vec[a].push_back(b);}if(flag){cout<<"INVALID"<<endl;continue;}int count=0;for (int i=1;i<=n;i++){if(bepointed[i]==false)bfs(i);elsecount++;}if(count==n){cout<<"INVALID"<<endl;continue;}int count2=0;for (int i=1;i<=n;i++)if(circle[i]==true)count2++;if(count2!=n) //value of count2 stands for the numbers of vertex that has been pushed into the queue.If it does not equal to n, loop exists{cout<<"INVALID"<<endl;continue;}if(flag) continue;int maxx=0;for (int i=1;i<=n;i++)maxx=max(maxx,dept[i]);int wid[102]={0};for (int i=1;i<=n;i++)wid[dept[i]]++;sort(wid,wid+102,cmp);cout<<maxx<<" "<<wid[0]<<endl;}return 0;
}这篇关于1034 forest的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
