#include <iostream> #include <algorithm> #include <cstdio> using namespace std; long long v[10001][10001]; bool visit[100001]; int n; void dfs(int node) { visit[node] = true; for(int i=1; i<=n; i++) { if(visit[i]==false && v[node][i] == 1) { dfs(i); } } } int main() { int m, k, a, b; scanf("%d%d", &n, &m); for(int i=0; i<m; i++) { scanf("%d%d", &a, &b); v[a][b] = 1; v[b][a] = 1; } fill(visit, visit+1001, false); int temp = 0; int block = 0; for(int j=1; j<=n; j++) { if(visit[j] == false) { dfs(j); block++; } } cout << block; return 0; }提高一下效率
时间: 2024-04-27 18:22:27 浏览: 36
#include <iostream>
可以尝试使用邻接表来存储图,这样可以减小空间复杂度。此外,可以使用迭代加深搜索(Iterative Deepening Search)代替深度优先搜索(DFS),这样可以避免深度过深导致的栈溢出问题,同时还能在保证正确性的前提下提高效率。另外,可以使用并查集(Union-Find)来实现连通块的计算,时间复杂度为O(mlogn),效率较高。
阅读全文