博客园同步

没有找到网上的题目，应该是道民间练习题。

并不是本人写的题，只是转载清晰一点吧。

原题链接

简要题意：

给定一个无向图，求连通块为树的个数。

显然，对于一个连通块，只要不出现环 那它就是树了。

那么就异常简单，一个个 dfs \text{dfs} dfs 就搞定了。

时间复杂度： O ( n + m ) O(n+m) O(n+m).

实际得分： 100 p t s 100pts 100pts.

细节：孤点也算一个连通块，也算一棵树。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+1; 

inline int read(){char ch=getchar(); int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

vector<int> G[N];
bool h[N],f=0; 
int n,m,s=0;

inline void dfs(int dep,int last) { //last 为上一个点
	if(h[dep]) return;
	h[dep]=1; //printf("%d %d\n",dep,last);
	//h 记录是否走过
	for(int i=0;i<G[dep].size();i++) {
		int u=G[dep][i];
		if(h[u] && u!=last) f=1; //出现环显然不行
		dfs(u,dep); //否则继续走
	}
}

int main() {
// freopen("tree.in","r",stdin);
// freopen("tree.out","w",stdout);
	n=read(),m=read(); while(m--) {
		int u=read(),v=read();
		G[u].push_back(v);
		G[v].push_back(u);
	} for(int i=1;i<=n;i++)
		if(!h[i]) { f=0;
			dfs(i,-1);
			if(!f) s++;
		} printf("%d\n",s);	
	return 0;
}