BZOJ 1116 POI2008 CLO 并查集

题目大意：给定一个无向图，求能否找到一个点和边的匹配，使匹配数为点数。

我又一次被并查集虐傻了。。。。

?

很好奇自信Dinic的话O(40W*√10W)的复杂度会不会T

估计会。。。

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define M 100100 using namespace std; int n,m; namespace Union_Find_Set{ int fa[M];bool flag[M]; int Find(int x) { if(!fa[x]||fa[x]==x) return fa[x]=x; return fa[x]=Find(fa[x]); } void Union(int x,int y) { x=Find(x);y=Find(y); if(x==y) { flag[x]=true; return ; } fa[x]=y;flag[y]|=flag[x]; } } int main() { using namespace Union_Find_Set; int i,x,y; cin>>n>>m; for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); Union(x,y); } for(i=1;i<=n;i++) if(!flag[Find(i)]) { puts("NIE"); return 0; } puts("TAK"); return 0; } 
     
    
   
  

?

?