[POI 19 Stage 2] Tour de Byteotia

作法：

以下稱編號 1 ~ k 的點為黑點，所以問題等價成要取最多的邊，使得黑點都不落在圈上。如果在一種邊的取法之中，有一條兩端點都不是黑點的邊沒有被取到，那麼加上這條邊之後，至多會形成一個包含黑點的圈（否則可以推出原本就有包含黑點的圈，矛盾），所以可以任意拔掉一條圈上的連接黑點的邊。由這個結論可以得到如果一條邊的兩端點都不是黑的，那麼一定可以取這條邊。所以一開始就先把所有的這種邊加進來，用並查集維護，把連接起來的點都縮成一坨。這樣問題就變成了要在好幾坨點和好幾個黑點之間加上最多條邊，使得加完之後不存在圈（注意到縮完之後任兩坨之間不會有任何邊）。而這也是用並查集就可以解決了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10 ;
 
struct P{int x,y;};
 
int fa[maxn] ;
int getfa(int x)
{
     return fa[x]==x ? x : fa[x]=getfa(fa[x]) ;
}
 
vector<P> v,ans ;
main()
{
     int n,m,k ; scanf("%d%d%d",&n,&m,&k) ;
     for(int i=1;i<=n;i++) fa[i]=i ;
     while(m--)
     {
          int x,y ; scanf("%d%d",&x,&y) ;
          if(x>k && y>k) fa[getfa(x)]=getfa(y) ;
          else v.push_back((P){x,y}) ;
     }
     for(int i=0;i<v.size();i++)
     {
          int x=getfa(v[i].x) , y=getfa(v[i].y) ;
          if(x==y) ans.push_back(v[i]) ;
          else fa[x]=y ;
     }
     printf("%d\n",ans.size()) ;
     for(int i=0;i<ans.size();i++) printf("%d %d\n",ans[i].x,ans[i].y) ;
}