# Finding connected components in the application task

I have n indexed socks, each of which has one of k colors. I also have a list that states which two socks I must wear at each of m days.

Of course I want always wear same color socks. But unfortunately I must follow the list. What I can do is to re-color some socks. The paint is expensive so I want to re-color the least possible number of socks. What is the number?

Input:

n m k
[color of sock 1] [color of sock 2] ... [color of sock n]
[pair for 1st day]
[pair for 2nd day]
...
[pair for mth day]


n, m and k are not larger than 200 000

Examples:

Input:

3 2 3
1 2 3
1 2
2 3


Output:

2


Input:

3 2 2
1 1 2
1 2
2 1


Output:

0


In my solution I find linked parts of socks. To do it I recursively look for socks which are in pair with one in any day (via dfs). All socks in a linked part must have one color. Now it's simple to determine how many socks must be re-painted in each linked part and to sum these numbers.

The problem is that my solution works rather slowly. It reaches the time limit (2000 ms) at the middle test. How do I improve my algorithm?

#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <stack>
using namespace std;

class Data {
int n_socks, n_days, n_colors;
vector<int> sock_color; // color of the sock
vector<set<int>> sock_with; // what socks are in pair with this
public:
Data() {
cin >> n_socks >> n_days >> n_colors;
sock_color.resize(n_socks);
for (auto & c: sock_color) {
scanf("%d", &c);
--c;
}
sock_with.resize(n_socks);
int l, r;
for (int i = 0; i < n_days; ++i) {
scanf("%d %d", &l, &r);
sock_with[l - 1].insert(r - 1);
sock_with[r - 1].insert(l - 1);
}
}
int compute() {
int sum = 0;
vector<bool> visited(n_socks);
int cur = 0; // first unvisited
while (true) {
visited[cur] = true;
vector<int> color_number(n_colors);
// how many socks of each color
// are linked with cur
++color_number[sock_color[cur]];

// let's find it via dfs:
stack<int> st;
st.push(cur);
while (!st.empty()) {
int u = st.top();
st.pop();
for (int v: sock_with[u]) {
if (!visited[v]) {
visited[v] = true;
++color_number[sock_color[u]];
st.push(v);
}
}
}

int max = 0, all = 0; // linked
for (int i: color_number) {
all += i;
if (i > max)
max = i;
}

// we should paint all except max
sum += all - max;

// finding next cur:
for (; cur < n_socks; ++cur)
if (!visited[cur])
break;
if (cur == n_socks)
break;
}
return sum;
}
};

int main() {
Data d;
cout << d.compute() << endl;
return 0;
}