旅游景点 （并查集）

旅游景点

描述 Description liouzhou_101住在柳侯公园附近，闲暇时刻都会去公园散散步。 很那啥的就是，柳侯公园的道路太凌乱了，假若不认识路就会走着走着绕回原来的那条路。 liouzhou_101就开始自己YY，假若给他当上那啥管理者，就会想尽量减少道路回圈的个数，但是大范围的改变道路终归不是什么良策。 经过调查，发现公园有N个景点，为了显示景点之间的优越性，我们按照1，2，…，N来把这N个景点编号，当然编号越小就说明越重要。 为了显示自己的英明决策，liouzhou_101决定，前K重要的景点最为重要，当然他们是标号为1…K了的。需要保证这K个景点不在任何一个环上，原因很简单，这前K个景点是很重要的景点，参观的人也很多，自然不会希望参观的人因为在兜圈子而迷路吧。 于是，我们所能够做的就是把之前建造好的一些道路清除掉，使得保证前K重要的景点不在任何一个环上。

输入格式 InputFormat 第一行包括三个正整数N，M和K，N表示景点的数量，M表示公园里的路径条数，K表示前K个景点最为重要。 再接下来M行，每行有两个正整数x和y，表示景点x和景点y之间有一条边。

输出格式 OutputFormat 仅一行，输出至少去除多少条路径，使得前K个重要的景点不在任何一个环上。 样例输入 11 13 5 1 2 1 3 1 5 3 5 2 8 4 11 7 11 6 10 6 9 2 3 8 9 5 9 9 10

样例输出

3

数据范围和注释 Hint 我们的删边方案是，删除(2,3)(5,9)(3,5)这三条边，这样节点1到5都不在任何一个环上。 而且可知删除三条边已经是最少的了。

30%的数据，满足N≤10，M≤20； 60%的数据，满足N≤1,000，M≤10,000； 100%的数据，满足N≤100,000，M≤200,000。 注意：给出的无向图可能有重边和自环。

读入数据的时候，如果一条路的两端都不在k的范围内，那么就可以直接合并，如果有一端在k之内，那么需要判断这两个端点是否已经在同一个集合中了，如果不在，可以合并，否则这就是一条需要出去的路径。

program mys;

var i,j,k,m,n,t:longint;
f,x,y:array[0..1000000]of longint;

function find(x:longint):longint;
begin 
if f[x]<>x then f[x]:=find(f[x]);
exit(f[x]);
end;

procedure union(x,y:longint);
begin 
x:=find(x);
y:=find(y);
if x<>y then f[x]:=y;
end;

begin 
assign(input,tou.in); reset(input);
assign(output,tou.out); rewrite(output);
readln(n,m,k);
for i:=1 to m do 
readln(x[i],y[i]);

for i:=1 to n do 
f[i]:=i;

for i:=1 to m do 
if (x[i]>k)and(y[i]>k) then 
union(x[i],y[i]);

for i:=1 to m do 
if (x[i]<=k)or(y[i]<=k) then 
if find(x[i])=find(y[i]) then 
inc(t)
else union(x[i],y[i]);

writeln(t);
close(input);
close(output);
end.