Submission #301862

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
int uf[32],used[32],eur[32];
int find(int a){
  if(uf[a]<0) return a;
  uf[a]=find(uf[a]);
  return uf[a];
}
void uni(int a,int b){
  if(find(a)==find(b)) return;
  if(uf[find(a)]<uf[find(b)]){
    uf[find(a)]=find(b);
    uf[find(b)]--;
  }
  else{
    uf[find(b)]=find(a);
    uf[find(a)]--;
  }
}
int main(void){
  for(int i=0;i<32;++i) uf[i]=-1;
  for(int i=0;i<32;++i) used[i]=0;
  int n;
  cin >> n;
  for(int i=0;i<n;++i){
    string tmp;
    cin >> tmp;
    uni(tmp[0]-'a',tmp[tmp.size()-1]-'a');
    used[tmp[0]-'a']++;
    used[tmp[tmp.size()-1]-'a']++;
  }
  for(int i=0;i<32;++i) eur[i]=0; 
  for(int i=0;i<26;++i){
    if(used[i]%2) eur[find(i)]++;
  }
  for(int i=0;i<32;++i) eur[i]/=2;
  for(int i=0;i<26;++i){
    if(used[i]) eur[find(i)]=max(eur[find(i)],1);
  }
  int answer=-1;
  for(int i=0;i<26;++i){
    answer+=eur[i];
  }
    
  cout << answer << endl;
  return 0;
}

Submission Info

Judge Result