Untitled

mail@pastecode.io avatarunknown
plain_text
25 days ago
1.2 kB
2
Indexable
Never
#include<bits/stdc++.h>
#define DilligentArch() ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0);
#define testcase(t) int t; cin>>t; while(t--)
#define pb push_back
typedef long long ll;
using namespace std;


const int N = 1e5+10;
vector<int>g[N];
bool vis[N];

vector<vector<int>>cc;
vector<int>cur_cc;

void dfs(int vertex){
   vis[vertex] = true;
   cur_cc.pb(vertex);
   for(int child : g[vertex]){
      if(vis[child]) continue;
      dfs(child);
   }
}

int main() {


   ios_base::sync_with_stdio(false);
   cin.tie(0), cout.tie(0);
   int t;
   cin>>t;
   while(t--){
    string blank;
    getline(cin,blank);
    getline(cin,blank);
    char c;
    cin>>c;
    int v,e;
    v=(int)c-65;

   // cout<<v<<endl;
   e=v;
   while(e--){
     char x,y;
     cin>>x>>y;

      g[(int)x-65].pb((int)y-65);
      g[(int)y-65].pb((int)x-65);
     // cout<<(int)x-65<< " "<<(int)y-65<<endl;
   }

   for(int i=0; i<v; i++){
      if(vis[i]) continue;
      cur_cc.clear();
      dfs(i);
      cc.pb(cur_cc);
   }

   cout << cc.size() << endl;
    //cout<<endl;

   memset(g,0,sizeof(g));
   memset(vis,0,sizeof(vis));
   cc.clear();
   cur_cc.clear();
}
}