This problem can be solved using dfs,bfs or union find algorithm,
BFS solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#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; } } |