CSDN 同步
没有找到网上的题目, 应该是道民间练习题.
并不是本人写的题, 只是转载清晰一点吧.
原题链接 https://www.luogu.com.cn/problem/U115442
简要题意:
给定一个无向图, 求连通块为树的个数.
显然, 对于一个连通块, 只要不出现环 那它就是树了.
那么就异常简单, 一个个 \(\text{dfs}\) 就搞定了.
时间复杂度:\(O(n+m)\).
实际得分:\(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",i)*/;
- } printf("%d\n",s);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3530559.html