Untitled
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(); } }