1 /**  2  * poj.org  3  * Problem#1274  4  * Accepted  5  * Time:16ms  6  * Memory:1980k  7  */  8 #include<iostream>  9 #include<sstream> 10 #include<cstdio> 11 #include<cmath> 12 #include<cstdlib> 13 #include<cstring> 14 #include<cctype> 15 #include<ctime> 16 #include<queue> 17 #include<set> 18 #include<map> 19 #include<stack> 20 #include<vector> 21 #include<algorithm> 22 using namespace std; 23 typedef bool boolean; 24 #define smin(a, b) (a) = min((a), (b)) 25 #define smax(a, b) (a) = max((a), (b)) 26 #define INF 0xfffffff 27 template<typename T> 28 inline boolean readInteger(T& u){ 29     char x; 30     int aFlag = 1; 31     while(!isdigit((x = getchar())) && x != ‘-‘ && ~x); 32     if(!(~x))    return false; 33     if(x == ‘-‘){ 34         aFlag = -1; 35         x = getchar(); 36     } 37     for(u = x - ‘0‘; isdigit((x = getchar())); u = u * 10 + x - ‘0‘); 38     ungetc(x, stdin); 39     u *= aFlag; 40     return true; 41 } 42 ///map template starts 43 typedef class Edge{ 44     public: 45         int end; 46         int next; 47         int cap; 48         int flow; 49         Edge(const int end = 0, const int next = 0, const int cap = 0, const int flow = 0):end(end), next(next), cap(cap), flow(flow){} 50 }Edge; 51  52 typedef class MapManager{ 53     public: 54         int ce; 55         int *h; 56         Edge *edge; 57         MapManager(){} 58         MapManager(int points, int limit):ce(0){ 59             h = new int[(const int)(points + 1)]; 60             edge = new Edge[(const int)(limit + 1)]; 61             memset(h, 0, sizeof(int) * (points + 1)); 62         } 63         inline void addEdge(int from, int end, int cap, int flow){ 64             edge[++ce] = Edge(end, h[from], cap, flow); 65             h[from] = ce; 66         } 67         inline void addDoubleEdge(int from, int end, int cap){ 68             addEdge(from, end, cap, 0); 69             addEdge(end, from, cap, cap); 70         } 71         Edge& operator [](int pos){ 72             return edge[pos]; 73         } 74         inline int reverse(int pos){        //反向边  75             return (pos & 1) ? (pos + 1) : (pos - 1); 76         } 77         inline void clear(){ 78             delete[] edge; 79             delete h; 80             ce = 0; 81         } 82 }MapManager; 83  84 #define m_begin(g, i)     (g).h[(i)] 85 #define m_end(g, i)     (g).edge[(i)].end 86 #define m_next(g, i)     (g).edge[(i)].next 87 #define m_cap(g, i)     (g).edge[(i)].cap 88 #define m_flow(g, i)     (g).edge[(i)].flow 89 ///map template ends 90  91 int n, m; 92 int t; 93 MapManager g; 94  95 inline boolean init(){ 96     if(!readInteger(n))    return false; 97     readInteger(m); 98     t = n + m + 1;  99     g = MapManager(t + 1, (n + 1) * (m + 1) * 2);100     for(int i = 1, a, b; i <= n; i++){101         readInteger(a);102         while(a--){103             readInteger(b);104             g.addDoubleEdge(i, b + n, 1);105         }106     }107     for(int i = 1; i <= n; i++)108         g.addDoubleEdge(0, i, 1);109     for(int i = 1; i <= m; i++)110         g.addDoubleEdge(i + n, t, 1);111     return true;112 }113 114 boolean *visited;115 int* divs;116 queue<int> que;117 118 inline boolean getDivs(){119     memset(visited, false, sizeof(boolean) * (t + 1));120     divs[0] = 1;121     visited[0] = true;122     que.push(0);123     while(!que.empty()){124         int e = que.front();125         que.pop();126         for(int i = m_begin(g, e); i != 0; i = g[i].next){127             int& eu = g[i].end;128             if(!visited[eu] && g[i].flow < g[i].cap){129                 divs[eu] = divs[e] + 1;130                 visited[eu] = true;131                 que.push(eu);132             }133         }134     }135     return visited[t];136 }137 138 int blockedflow(int node, int minf){139     if(node == t || minf == 0)    return minf;140     int f, flow = 0;141     for(int i = m_begin(g, node); i != 0; i = m_next(g, i)){142         int& e = g[i].end;143         if(divs[e] == divs[node] + 1 && visited[e] && (f = blockedflow(e, min(minf, g[i].cap - g[i].flow))) > 0){144             flow += f;145             g[i].flow += f;146             g[g.reverse(i)].flow -= f;147             minf -= f;148             if(minf == 0)    return flow;149         }150     }151     return flow;152 }153 154 inline int maxflow(){155     visited = new boolean[(const int)(t + 1)];156     divs = new int[(const int)(t + 1)];157     int res = 0;158     while(getDivs()){159         res += blockedflow(0, INF); 160     }161     return res;162 }163 164 inline void solve(){165     int res = maxflow();166     cout << res << endl;167 }168 169 inline void clear(){170     delete[] visited;171     delete[] divs;172     g.clear();173 }174 175 int main(){176     while(init()){177         solve();178         clear();179     }180     return 0;181 }