Itsy's Magic Cards
Limits 1s, 512 MB
Itsy needs your help with her magic cards. Her magic cards grant her special spider-witch powers.
Unfortunately, some of the magic cards are a bit strange. Whenever they come close to each other, they react and vanish into thin air.
Itsy has N magic cards in front of her right now, and she wants to find the maximum number of cards that she can stack together without having to worry about them vanishing.
Input
The input starts with two integers, N (0 < N < 18) and M (0 < M < 10). N represents the number of cards Itsy has in front of her.
The following M lines will contain two uppercase alphabets each representing the two cards that would react and vanish if they come to close to each other. The alphabets will always be valid (i.e. only the first N alphabets may appear in these M lines).
Output
Print the maximum number of cards that Itsy can keep together without having to worry about the cards vanishing.
Sample
| Input | Output |
|---|---|
6 2 A B B E | 5 |
In this case, the cards A and B (and, cards B and E) cannot be chosen together. The maximum number of cards can be chosen by ignoring B.
| |
Solution:
#include <bits/stdc++.h> using namespace std; bool check(vector<vector<int> > &g){ for(auto i:g){ for(auto j:i){ if(j){ return true; } } } return false; } int main() { int n, m; cin>>n>>m; vector<vector<int> > g(n, vector<int>(n, 0)); for(int i=0;i<m;i++){ char a, b; cin>>a>>b; g[a-'A'][b-'A']=1; g[b-'A'][a-'A']=1; } int res=n; while(check(g)){ int mx=0, to=0; for(int i=0;i<n;i++){ int cnt=0; for(auto j:g[i]){ cnt+=j; } if(cnt>mx){ mx=cnt; to=i; } } for(int i=0;i<n;i++){ if(g[to][i]){ g[to][i]=0; g[i][to]=0; } } res--; } cout<<res; return 0; }
0 Comments