• 并查集的做法

暂时还不会。

• 二分图

思路很可以

超时的问题：即使把vis改成bool还是超，于是了解了“时间戳”QwQ（还是很好理解的）

原来memset真的还是挺费时间的

所以二分图这个时间戳的写法真的可以了解一下

#include
    
     #include
     
      #define ll intusing namespace std;int n,head[5000005],match[5000005],vis[5000005],cnt,ans,maxx,timechuo;inline int max(int x,int y){return x>y?x:y;}struct edge{    int v,next;}e[5000005];inline void add(int u,int v){    e[++cnt].v=v;    e[cnt].next=head[u];    head[u]=cnt;}inline bool dfs(int u){    for(int i=head[u];i!=-1;i=e[i].next){        if(vis[e[i].v]!=timechuo){            vis[e[i].v]=timechuo;            if(match[e[i].v]==-1||dfs(match[e[i].v])){                match[e[i].v]=u;                return 1;            }        }    }    return 0;}inline void input(ll &x){    ll ans=0,f=1;    char c=getchar();    while(c>'9'||c<'0'){        if(c=='-')f=-1;        c=getchar();    }    while(c>='0'&&c<='9'){        ans=ans*10+c-48;        c=getchar();    }    x=ans*f;}inline void output(ll x){    if(x<0)x=-x,putchar('-');    if(x>9)output(x/10);    putchar(x%10+48);}inline void writeln(ll x){    output(x);    putchar('\n');}int main(){    memset(head,-1,sizeof(head));    memset(match,-1,sizeof(match));    input(n);    for(int i=1;i<=n;i++){        int x,y;        input(x);input(y);        add(x,i);add(y,i);        maxx=max(maxx,x);maxx=max(maxx,y);    }    for(int i=1;i<=maxx;i++){        timechuo=i;        int temp=dfs(i);        if(!temp)break;        else ans++;    }    writeln(ans);}