459

This problem can be solved using dfs,bfs or union find algorithm,

BFS solution:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <map>
#include <queue>
#include <string>

using namespace std;

int to;
bool visit[26];
int graph[26][26];

void bfs(int a)
{
	int b;
	queue<int> q;
	q.push(a);

	while(!q.empty())
	{
		b =q.front();
		q.pop();
		visit[b]=1;
		for(int i=0;i<=to;i++)
		{
			if(graph[b][i]==1 && visit[i]==0)
			{
				q.push(i);
				visit[i]=1;
				graph[b][i]=0;
				graph[i][b]=0;
			}

		}
	}
}

int main()
{
	int t,c=0;
	string s;
	cin>>t;
	scanf("\n");

	while(t--)
	{
		getline(cin,s);
		to = s[0]-65;
		memset(graph,0,sizeof(graph));
		memset(visit,0,sizeof(visit));
		while(1)
		{
			getline(cin,s);
			if(s=="")
			break;
			graph[s[0]-65][s[1]-65]=1;
			graph[s[1]-65][s[0]-65]=1;
		}
		int cnt=0;
		for(int i=0;i<=to;i++)
		{
			if(visit[i]==0)
			{
				bfs(i);
				cnt++;
			}

		}


		cout<<cnt<<endl;
		if(t)
		cout<<endl;

		if(c==t)
		break;
	}
}