Một số khái niệm về lập trình và ngôn ngữ lập trình

Bạn chưa đăng nhập. Vui lòng đăng nhập để hỏi bài
Anh Phạm
31 tháng 7 2021 lúc 19:59

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;

vector<int> edge[maxn];
int f[maxn];
bool visited[maxn];

void dfs(int u) {
  visited[u] = true;
  f[u] = 1;
  for (int v : edge[u]) {
    if (!visited[v]) {
      dfs(v);
      f[u] += f[v];
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    edge[u].push_back(v);
    edge[v].push_back(u);
  }
  vector<int> components;
  for (int i = 1; i <= n; i++) {
    if (!visited[i]) {
      dfs(i);
      components.push_back(f[i]);
    }
  }
  int res = components.front();
  int rest = 0;
  for (int i = 1; i < components.size(); i++) {
    rest = max(rest, components[i]);
  }
  cout << res + rest << endl;
}

 


Các câu hỏi tương tự
Mai Lan Hương
Xem chi tiết
Dang Dinh Trong
Xem chi tiết
Phạm Hoài An
Xem chi tiết