可以跑二分图

到第一个不能匹配的点就退出

嗯 还有并查集判环的做法？

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 8 using namespace std; 9 10 void setIO(const string& a) {11 freopen((a+".in").c_str(), "r", stdin);12 freopen((a+".out").c_str(), "w", stdout);13 }14 15 const int N = 1000000 + 10, M = 10000 + 10;16 17 #include
           
            18 vector
            
              G[M];19 int mat[M];20 21 void AddEdge(int u, int v) {22 G[u].push_back(v);23 }24 25 int vis[N], clk;26 27 bool find(int u) {28 for(unsigned i = 0; i < G[u].size(); i++) {29 int v = G[u][i];30 if(vis[v] != clk) {31 vis[v] = clk;32 if(mat[v] == 0 || find(mat[v])) {33 mat[v] = u;34 return 1;35 }36 }37 }38 return 0;39 }40 41 int work(int n) {42 for(int i = 1; i <= n; i++) {43 ++clk;44 if(!find(i)) return i - 1;45 }46 return n;47 }48 49 int main() {50 int x, y, n;51 scanf("%d", &n);52 for(int i = 1; i <= n; i++) {53 scanf("%d%d", &x, &y);54 AddEdge(x, i);55 AddEdge(y, i);56 }57 printf("%d\n", work(n));58 59 return 0;60 }