求助
  • 板块学术版
  • 楼主mimangxiaoshuye
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/5/22 22:23
  • 上次更新2023/10/28 00:48:25
查看原帖
求助
575992
mimangxiaoshuye楼主2022/5/22 22:23

题目:给定无权无向图G(V,E),判断G是否是一棵树。

代码:

#include<bits/stdc++.h>
using namespace std;
int t;
const int N=5000*2+5;
int n,m,u,v;
vector<int> e[N];
int sum;
bool vi[N];
int fa[N];

void dfs(int u,int pa){
	vi[u]=1;fa[u]=pa;
	for(int i : e[u]) if(i!=pa){
        sum++;
		dfs(i,u);
	}
}
bool tree(){
	dfs(1,0);
	sum/=2;
	if(sum!=n-1) return 0;
	for(int i=1;i<=n;i++)
		if(vi[i]==0) return 0;

	return 1;
}
int main(){
	cin>>t;
	while(t--){
        sum=0;
		for(int i=1;i<=N;i++){
			e[i].clear();
		}
		memset(vi,0,sizeof(vi));
		cin>>n>>m;
		while(m--){
			cin>>u>>v;
			e[u].push_back(v);
			e[v].push_back(u);

		}
		if(tree()==0){
            cout<<"not tree"<<endl;
		}
		else cout<<"tree"<<endl;

	}
	return 0;
}

没有输出,不知道为啥,求大佬调代码

2022/5/22 22:23
加载中...