企业官网建设流程全解析

链接：547. 省份数量

题解：力扣

class Solution { public: int findCircleNum(vector<vector<int>>& M) { std::unordered_map<int, vector<int>> edges; // 构建邻接矩阵 for(int i = 0; i < M.size(); ++i) { for(int j = 0; j < M[i].size(); ++j) { if(M[i][j] == 1) { edges[i].push_back(j); edges[j].push_back(i); } } } // 标记结点是否访问过 std::unordered_map<int, bool> visited; int cnt = 0; // 以每个城市为顶点 for(int i = 0; i < M.size(); ++i) { if(visited.find(i) == visited.end()) { ++cnt; std::queue<int> que; que.push(i); // 标记访问过的结点 visited[i] = true; while(!que.empty()) { int front = que.front(); que.pop(); for(auto& node : edges[front]) { // 如果这个结点没访问过 if(visited.find(node) == visited.end()) { que.push(node); // 标记访问过的结点 visited[node] = true; } } } } } return cnt; } };

class UnionFind { public: UnionFind():_count(0) { } void add(int p) { _father[p] = p; _size[p] = 1; ++_count; } void merge(int p, int q) { int p_root = find(p); int q_root = find(q); if (p_root != q_root) { _father[p_root] = q_root; _size[q_root] += _size[p_root]; --_count; } } bool is_connected(int p, int q){ return find(p) == find(q); } int get_size(int p) { return _size[find(p)]; } int get_count() { return _count; } private: int find(int p) { while (_father[p] != p) { p = _father[p]; } return p; } private: std::unordered_map<int, int> _father; std::unordered_map<int, int> _size; int _count; }; class Solution { public: int findCircleNum(vector<vector<int>>& isConnected) { if (isConnected.size() <= 0) { return 0; } int n = isConnected[0].size(); UnionFind uf; for (int i = 0; i < n; ++i) { uf.add(i); } for (int i = 0; i < isConnected.size(); ++i) { for (int j = 0; j < isConnected[0].size(); ++j) { if (i == j || isConnected[i][j] == 0) { continue; } if (uf.is_connected(i, j)) { continue; } uf.merge(i, j); } } return uf.get_count(); } };

class Solution { public: int findCircleNum(vector<vector<int>>& isConnected) { int len = isConnected.size(); if (len <= 0) { return 0; } std::unordered_map<int, std::unordered_set<int>> graph; for (int i = 0; i < isConnected.size(); ++i) { for (int j = 0; j < isConnected[i].size(); ++j) { if (!isConnected[i][j]) { continue; } graph[i].insert(j); graph[j].insert(i); } } int result = 0; std::vector<bool> visited(isConnected.size(), false); for (int i = 0; i < isConnected.size(); ++i) { if (visited[i]) { continue; } ++result; bfs(i, graph, visited); } return result; } private: void bfs(int i, std::unordered_map<int, std::unordered_set<int>>& graph, std::vector<bool>& visited) { std::queue<int> que; que.push(i); visited[i] = true; while (!que.empty()) { auto f = que.front(); que.pop(); for (auto neigh : graph[f]) { if (visited[neigh]) { continue; } visited[neigh] = true; que.push(neigh); } } } };