POJ.2724 Purifying Machine

1.Problem
http://poj.org/problem?id=2724

2.Idea
Bipartite Matching

3.Source

 #define MAX_V 2222  
 int V;  
 vector<int> G[MAX_V];  
 int match[MAX_V];  
 bool used[MAX_V];  
 int N, M;  
 vector<string> vs;  
 bool isConnected(int i, int j)  
 {  
      int cnt = 0;  
      for (int k = 0; k < N; k++) {  
           if (vs[i][k] != vs[j][k]) cnt++;  
      }  
      return cnt == 1;  
 }  
 void add_edge(int u, int v)  
 {  
      G[u].push_back(v);  
      G[v].push_back(u);  
 }  
 bool dfs(int v)  
 {  
      used[v] = true;  
      for (int i = 0; i < G[v].size(); i++) {  
           int u = G[v][i], w = match[u];  
           if (w < 0 || !used[w] && dfs(w)) {  
                match[v] = u;  
                match[u] = v;  
                return true;  
           }  
      }  
      return false;  
 }  
 int bipartite_matching()  
 {  
      int res = 0;  
      memset(match, -1, sizeof match);  
      for (int v = 0; v < V; v++) {  
           if (match[v] < 0) {  
                memset(used, 0, sizeof used);  
                if (dfs(v)) {  
                     res++;  
                }  
           }  
      }  
      return res;  
 }  
 void solve()  
 {  
      for (int i = 0; i <= V; i++) G[i].clear();  
      memset(used, 0, sizeof used);  
      vs.clear();  
      for (int i = 0; i < M; i++) {  
           string s, t;  
           cin >> s;  
           t = s;  
           int j = 0;  
           for (j = 0; j < N; j++) {  
                if (s[j] == '*') break;  
           }  
           if (j < N) {  
                s[j] = '1';  
                t[j] = '0';  
                vs.push_back(s);  
                vs.push_back(t);  
           }  
           else {  
                vs.push_back(s);  
           }  
      }  
      sort(vs.begin(), vs.end());  
      vs.erase(unique(vs.begin(), vs.end()), vs.end());  
      V = vs.size();  
      for (int i = 0; i < V; i++)  
           for (int j = i + 1; j < V; j++) {  
                if (isConnected(i, j)) {  
                     add_edge(i, j);  
                }  
           }  
      printf("%d\n", V - bipartite_matching());  
 }  
 int main()  
 {  
      while (scanf("%d%d", &N, &M)>0) {  
           if (N + M == 0) break;  
           solve();  
      }  
      return 0;  
 }