daily pastebin goal
22%
SHARE
TWEET

Untitled

a guest Jun 13th, 2018 45 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define _ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  4. typedef long long ll ;
  5.  
  6.  
  7. int n,m,cnt;
  8. vector<vector<int> > g;
  9. bool vis[10001];
  10. vector<int> v;
  11. void dfs(int u) {
  12.     vis[u] = 1;
  13.  
  14.     for (int i = 0; i < g[u].size(); i++)
  15.         if (!vis[g[u][i]]){
  16.             cnt++;
  17.             dfs(g[u][i]);
  18.         }
  19. }
  20.  
  21. int main(){_
  22.  //freopen("Graphs again.in","r", stdin);
  23.     int t;
  24.     cin >> t ;
  25.     while(t--){
  26.     scanf("%d%d", &n, &m);
  27.     g.clear();
  28.     g.resize(n);
  29.     for (int i = 0; i < m; i++) {
  30.         int a, b;
  31.         scanf("%d%d", &a, &b);
  32.         g[a].push_back(b);
  33.         g[b].push_back(a);
  34.     }
  35.     memset(vis, 0, sizeof(vis));
  36.     v.clear();
  37.     for(int i=0;i<n;i++){
  38.             cnt=0;
  39.         if(!vis[i])
  40.             dfs(i);
  41.         v.push_back(cnt);
  42.     }
  43.     sort(v.begin(),v.end(),greater<int>());
  44.     cout << v[0]+v[1] << endl ;
  45. }
  46. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top