P1640[SCOI] 连续攻击游戏

https://www.luogu.com.cn/problem/P1640 两种做法：

【1】我们可以发现老套路，这种一个物体连接两个结点的一般是物体做边连接两个点来构成一张图。然后我们从1开始选择，每选择一个就删去一条边。记住如果当前图上有环的话，可以多选一条边。 至于怎么维护这个关系，带权并查集就很简单 细节看代码 DSU()函数

【2】数据10000，二分图的最大匹配可以尝试做一做。第i件物品连接u和v数字，然后从1开始做最大匹配，直到第一次不能匹配位置，有点像关押罪犯那道题。记住二分图一开始的板子是直接memset，这样会超时，因此我们呢需要用一个栈记录哪些点被vis过了，每次循环最后再清空即可。 细节看代码BF()函数

#include<unordered_set>
#include<unordered_map>
#include<functional>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<iterator>
#include<cstring>
#include<numeric> 
#include<cstdio>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<map>

using namespace std;
//================================
#define debug(a) cout << #a": " << a << endl;
#define rep(i, ll,rr) for(int i = ll; i <= rr; ++i)
// #define N 100010
//================================
typedef pair<int,int> pii;
#define x first
#define y second
typedef long long LL; typedef unsigned long long ULL; typedef long double LD;
inline LL read() {
          
    LL s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == -) w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(LL x, int op = 10) {
          
    if (!x) {
          
    putchar(0); if (op)  putchar(op); return; }  char F[40]; LL tmp = x > 0 ? x : -x; if (x < 0)putchar(-);  int cnt = 0;    while (tmp > 0) {
          
    F[cnt++] = tmp % 10 + 0;     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op) putchar(op); }
LL fpower(LL a,LL b,LL mod) {
          
   LL ans = 1; while(b){
          
    if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; } LL Mod(LL a,LL mod){
          
   return (a%mod+mod)%mod;}
//=================================图论题老规矩先开一堆数组...
const int N = 1e6+10,M=10005;
int pa,pb,a,b,n,m,fa[N],cir[N],cnt[N],tt=0;
int e[N*2],ne[N*2],h[N],idx=0,match[N],vis[N],stk[N];
//=================================二分图做法
void add(int a,int b) {
          
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
bool dfs(int x) {
          
   
    for(int i=h[x];~i;i=ne[i]){
          
   
        int j = e[i];
        if(vis[j]) continue;
        stk[++tt] = j;
        vis[j] = true;
        if(!match[j] || dfs(match[j])){
          
   
            match[j] = x;
            return true;
        }
    } return false;
}
void BF(){
          
   
    memset(h,-1,sizeof h);
    n = read();
    rep(i,1,n) {
          
   
        a = read() , b = read();
        add(a,i); add(b,i);
    }
    rep(i,1,n+1){
          
   
    	tt=0;
        if(!dfs(i)){
          
   
            print(i-1);
            return ;
        }
        while(tt) vis[stk[tt--]] = 0; 
    }
    return ;
}
//=================================并查集做法
void init() {
          
   rep(i,1,10000) fa[i] = i , cnt[i] = 1;}
int find(int x) {
          
   return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);}
void DSU(){
          
   
    int ans = 0;
    init();
    
    n = read();
    rep(i,1,n){
          
   
        a = read() , b = read();
        pa = find(a),pb = find(b);
        if(pa!=pb){
          
   
            fa[pa] = pb;
            cnt[pb] += cnt[pa];
            if(cir[pa]) cir[pb] = 1;
        }
        else
            cir[pa] = 1;
    }
    int p;
    rep(i,1,10000){
          
   
        p = find(i);
        if(cnt[p]>1) {
          
   
            cnt[p] --;
            ans++;
        }
        else if(cir[p]) ans++,cir[p] = false;
        else break;
    }
    print(ans);
	return ;
}
//=================================
signed main(){
          
   
    BF();
//     DSU();
    return 0;
}