fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. vector<int> adj[27];
  7. bool used[27];
  8. int current_size = 0;
  9.  
  10. void dfs(int node) {
  11.     used[node] = true;
  12.     current_size++;
  13.     for (int neighbor : adj[node]) {
  14.         if (!used[neighbor]) {
  15.             dfs(neighbor);
  16.         }
  17.     }
  18. }
  19.  
  20. int main() {
  21.     // Example: assuming a and b are strings of the same length
  22.     string a = "hello";
  23.     string b = "world";
  24.     int n = a.length();
  25.  
  26.     // Build the graph
  27.     for (int i = 0; i < n; i++) {
  28.         if (a[i] != b[i]) {
  29.             int u = a[i] - 'a' + 1;
  30.             int v = b[i] - 'a' + 1;
  31.             adj[u].push_back(v);
  32.             adj[v].push_back(u);
  33.         }
  34.     }
  35.  
  36.     int ans = 0;
  37.  
  38.     // Traverse the components
  39.     for (int i = 1; i <= 26; i++) {
  40.         // We only care about unvisited nodes that are actually part of an edge
  41.         if (!used[i] && !adj[i].empty()) { 
  42.             current_size = 0;
  43.             dfs(i);
  44.             ans += (current_size - 1);
  45.         }
  46.     }
  47.  
  48.     cout << ans << endl;
  49.     return 0;
  50. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
https://ideone.com/0z0Fcm
language:
C++ (gcc 8.3)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!