二分图不想讲
最小点覆盖就行 每个边是一个小行星
Code:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 #define inf 2147483647 6 #define ms(a,b) memset(a,b,sizeof a) 7 #define rep(i,a,n) for(int i = a;i <= n;i++) 8 #define per(i,n,a) for(int i = n;i >= a;i--) 9 using namespace std; 10 typedef long long ll; 11 inline int read() { 12 int as = 0,fu = 1; 13 char c = getchar(); 14 while(c < '0' || c > '9') { 15 if(c == '-') fu = -1; 16 c = getchar(); 17 } 18 while(c >= '0' && c <= '9') { 19 as = as * 10 + c - '0'; 20 c = getchar(); 21 } 22 return as * fu; 23 } 24 const int N = 200005; 25 //head 26 int n,m,ans; 27 int head[N],mo[N<<1],nxt[N<<1],cnt; 28 void add(int x,int y) { 29 mo[++cnt] = y; 30 nxt[cnt] = head[x]; 31 head[x] = cnt; 32 return; 33 } 34 int match[N],vis[N]; 35 bool dfs(int x,int tm) { 36 for(int i = head[x];i;i = nxt[i]) { 37 int sn = mo[i]; 38 if(vis[sn] == tm) continue; 39 vis[sn] = tm; 40 if(!match[sn] || dfs(match[sn],tm)) { 41 match[sn] = x; 42 return 1; 43 } 44 } 45 return 0; 46 } 47 48 int main() { 49 n = read(),m = read(); 50 rep(i,1,m) add(read(),read()+n); 51 rep(i,1,n<<1) ans += dfs(i,i); 52 printf("%d ",ans); 53 return 0; 54 }