Advertisement
fooker

largest size of connected component

Mar 13th, 2023
165
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.17 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. ll max_ll(ll x, ll y){
  5. return ((x>y)?(x):(y));
  6. }
  7. int main()
  8. {
  9.     ll n,m;
  10.     cin>>n>>m;
  11.     vector<ll> adj[n+1];
  12.     map <pair<ll,ll>,ll> mp;
  13.     for (ll i=1; i<=m; i++){
  14.         ll x,y;
  15.         cin>>x>>y;
  16.         if ((x>=y && mp[make_pair(x,y)]<1) || (x<y && mp[make_pair(y,x)]<1)){
  17.             adj[x].push_back(y);
  18.             adj[y].push_back(x);
  19.             if (x>=y) mp[make_pair(x,y)]++;
  20.             else mp[make_pair(y,x)]++;
  21.         }
  22.     }
  23.     ll groups=0, ans=0;
  24.     vector <bool> visited(n+1,false);
  25.     for (ll i=1; i<=n; i++){
  26.         if(!visited[i]){
  27.             visited[i]=true;
  28.             groups++;
  29.             queue <ll> q;
  30.             q.push(i);
  31.             while(!q.empty()){
  32.                 ll v=q.front();
  33.                 q.pop();
  34.                 for (auto u:adj[v]){
  35.                     if (!visited[u]){
  36.                         visited[u]=true;
  37.                         groups++;
  38.                         q.push(u);
  39.                     }
  40.                 }
  41.             }
  42.         }
  43.         ans=max_ll(ans,groups);
  44.         groups=0;
  45.     }
  46.     cout<<ans<<"\n";
  47. }
  48.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement