fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int inf = 1e9;
  5.  
  6. void solve() {
  7.     int n, m;
  8.     cin >> n >> m;
  9.     vector<vector<int>> G(n+1);
  10.     vector<bool> czy_odwiedzony(n+1, false);
  11.  
  12.     for (int i = 0; i < m; i++) {
  13.         int u, v;
  14.         cin >> u >> v;
  15.         G[u].push_back(v);
  16.         G[v].push_back(u);
  17.     }
  18.  
  19.     int max_rozmiar = 0;
  20.  
  21.     for (int i = 1; i <= n; i++) {
  22.         if (czy_odwiedzony[i]) {
  23.             continue;
  24.         }
  25.  
  26.         queue<int> kol;
  27.         kol.push(i);
  28.         czy_odwiedzony[i] = true;
  29.         int akt_rozmiar = 1;
  30.  
  31.         while (!kol.empty()) {
  32.             int v = kol.front();
  33.             kol.pop();
  34.  
  35.             for (int sasiad: G[v]) {
  36.                 if (!czy_odwiedzony[sasiad]) {
  37.                     kol.push(sasiad);
  38.                     czy_odwiedzony[sasiad] = true;
  39.                     akt_rozmiar++;
  40.                 }
  41.             }
  42.         }
  43.  
  44.         max_rozmiar = max(max_rozmiar, akt_rozmiar);
  45.     }
  46.  
  47.     cout << max_rozmiar << '\n';
  48. }
  49.  
  50. int main() {
  51.  
  52.     int d;
  53.     cin >> d;
  54.     for (int i = 0; i < d; i++) {
  55.         solve();
  56.     }
  57.  
  58.  
  59.     return 0;
  60. }
  61.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
2
4 3
1 2
2 3
3 4
9 7
2 1
1 9
3 4
4 5
7 5
4 8
4 7
stdout
copy 
4
5
https://ideone.com/ljjFjW
language:
C++14 (gcc 8.3)
created:
18 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!