找到
1
篇与
状态压缩
相关的结果
-
C++求联通块数量 本文使用了下面五种方法求联通块数量： 并查集 深度优先搜索DFS 广度优先搜索BFS Floyd Kruskal #include<bits/stdc++.h> using namespace std; const int N = 110; const int M = 10010; int n, m; vector<int> g[N]; int ans = 0; // 1.并查集 int pre[N]; int find ( int x ) { return x == pre[x] ? pre[x] : pre[x] = find ( pre[x] ); } void merge ( int x, int y ) { int rx = find ( x ), ry = find ( y ); if ( rx != ry ) { pre[rx] = ry; } } void solveA() { for ( int i = 1; i <= n; i++ ) { pre[i] = i; } for ( int i = 1; i <= m; i++ ) { int u, v; cin >> u >> v; g[u].emplace_back ( v ); g[v].emplace_back ( u ); merge ( u, v ); } for ( int i = 1; i <= n; i++ ) { if ( pre[i] == i ) { ans++; } } cout << ans; } // 2.深搜 int vis[N]; void dfs ( int x ) { for ( auto &u : g[x] ) { if ( vis[u] ) { continue; } vis[u] = true; dfs ( u ); } } void solveB() { for ( int i = 1; i <= m; i++ ) { int u, v; cin >> u >> v; g[u].emplace_back ( v ); g[v].emplace_back ( u ); } for ( int i = 1; i <= n; i++ ) { if ( !vis[i] ) { dfs ( i ); ans++; } } cout << ans; } // 3.广搜 void bfs ( int x ) { queue<int> q; q.emplace ( x ); while ( !q.empty() ) { int u = q.front(); q.pop(); for ( auto &v : g[u] ) { if ( vis[v] ) { continue; } vis[v] = true; q.emplace ( v ); } } } void solveC() { for ( int i = 1; i <= m; i++ ) { int u, v; cin >> u >> v; g[u].emplace_back ( v ); g[v].emplace_back ( u ); } for ( int i = 1; i <= n; i++ ) { if ( !vis[i] ) { bfs ( i ); ans++; } } cout << ans; } // 4.Floyd int adj[N][N]; void solveD() { for ( int i = 1; i <= n; i++ ) { adj[i][i] = 1; } for ( int i = 1; i <= m; i++ ) { int u, v; cin >> u >> v; adj[u][v] = adj[v][u] = 1; } ans = 0; for ( int k = 1; k <= n; k++ ) { for ( int i = 1; i <= n; i++ ) { for ( int j = 1; j <= n; j++ ) { if ( adj[i][k] && adj[k][j] ) { adj[i][j] = 1; } } } } for ( int i = 1; i <= n; i++ ) { if ( !vis[i] ) { ans++; for ( int j = 1; j <= n; j++ ) { if ( adj[i][j] ) { vis[j] = true; } } } } cout << ans; } // 5.Kruskal 最小生成森林 struct Edge { int u, v; } e[M]; void solveE() { for ( int i = 1; i <= n; i++ ) { pre[i] = i; } for ( int i = 1; i <= m; i++ ) { int u, v; cin >> u >> v; e[i] = {u, v}; } ans = n; for ( int i = 1; i <= m; i++ ) { int u = e[i].u, v = e[i].v; int ru = find ( u ), rv = find ( v ); if ( ru != rv ) { merge ( ru, rv ); ans--; } } cout << ans; } // int main() { cin >> n >> m; // solveA(); // solveB(); // solveC(); // solveD(); solveE(); return 0; }
