陈亮
(小黑子)
1
题目描述
树是一种常见的数据结构.
一棵树的根节点只有一个，并且没有其他点指向它.从根节点遍历有向边，我们只会得到唯一的一个序列.
例如，下图中前两个例子是树，第三个不是：
给你�t张有向图，请你判断每张图是否是一颗树.
输入格式
第一行包含一个正整数�(1≤�≤2000)t(1≤t≤2000),表示测试数据组数
对于每个测试数据，第一行包含两个整数�n和�m (2≤�≤200000;1≤�≤200000(2≤n≤200000;1≤m≤200000,表示图的点数和边数.
接下来�m行每行包含两个整数�u和�v (1≤�,�≤�,�≠�)(1≤u,v≤n,u=v),代表一条�u指向�v的边.
数据保证没有重边和自环.
对于所有测试数据，数据总量不超过2∗1052∗105.
输出格式
对于每个测试数据，输出"Case k is a tree.“如果第�k个测试数据是一棵树，否则输出"Case k is not a tree.”
样例#1
样例输入#1
3
6 5
5 6
4 2
4 1
5 3
4 5
9 8
8 1
7 3
6 2
8 9
7 5
7 4
7 8
7 6
6 6
2 6
5 6
5 3
4 2
4 5
4 1
样例输出#1
Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.
我的代码
#include<bits/stdc++.h>
using namespace std;
int sum=1;
void solve(){
int n,m,d[200005]={0};
cin>>n>>m;
for(int i=1,x,y;i<=m;i++){
cin>>x>>y;
d[y]++;
}
sort(d+1,d+n+1);
cout<<"Case "<<sum<<" is ";
if(d[n]>1 || n-m!=1){
cout<<"not ";
}
cout<<"a tree."<<endl;
sum++;
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
}
2 个赞
周子寓
(zzy10124)
8
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0,t,cnt=0,sum=0;
int vis[200010],b[200010];
vector<int> a[200010];
//char a[1010][1010];
void dfs(int x){
vis[x]=1;//标记这个点
sum++;//点数
int len=a[x].size();
for(int i=0;i<len;i++){
if(vis[a[x][i]]==0) dfs(a[x][i]);//不回走
}
}
int main(){
cin>>t;
for(int num=1;num<=t;num++){//t组数据
memset(vis,0,sizeof vis);//初始化
cnt=ans=0;
cin>>n>>m;
for(int i=1;i<=n;i++){//清空树
a[i].clear();
}
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
a[x].push_back(y); //有向树存储
}
if(n!=(m+1)){
printf("Case %d is not a tree.\n",num);//因为树的点数一定比边数多1，所以可以特判。
continue;
}
for(int i=1;i<=n;i++){
memset(vis,0,sizeof vis);
sum=0;
dfs(i);//遍历每个点，找到根结点。
if(sum==n){//如果当前点可以遍历到所有点，说明是根结点，那就可以判断为一棵树。
printf("Case %d is a tree.\n",num);
ans=1;
break;
}
}
if(ans==0) printf("Case %d is not a tree.\n",num);//没有根结点就不是树了
}
}
1 个赞
周子寓
(zzy10124)
9
（代码作为参考）思路：只要找到根节点就可以判断它是树了。
根节点：从这个点出发可以到达所有点
周子寓
(zzy10124)
10
代码实现：
dfs（）{
标记
记录点数
if（下一个点可以走）dfs(下一个点)
}
可以的话给个解决方案
1 个赞
凌浩诚
(人老，心不老)
11
在输入一个DAG时统计每个节点的入度，递增边数，输入结束后先判断边数是否==节点数-1，如果不是，那就不是一棵树，如果是，再枚举每一个节点，如果有两个及以上的节点入度为0，那就不是一棵树，如果有且仅有一个，那就是一棵树
理论上能行
时间复杂度为 O(V) ， V 为节点个数
2 个赞
凌浩诚
(人老，心不老)
12
其实不用，只要这个图是个连通图，如果仅一个点的入度为0，它就是root
2 个赞