282 条题解
-
0
mintalfance LV 10 @ 2009-09-11 11:50:56
program p1034;
var a:array[1..5000] of longint;
i,j,k,l,m,n,p,q,r:longint;
begin
for i:=1 to 5000 do a[i]:=i;
readln(n,m,r);
for i:=1 to m do
begin readln(p,q);
for j:=1 to n do
if (a[j]=a[q]) and (jq) then a[j]:=a[p];
a[q]:=a[p];
end;
for i:=1 to r do begin
readln(p,q);if a[p]=a[q] then writeln('Yes') else writeln('No');
end;
end.第一次写并查集。。。练手
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms并查集第一题——纪念………
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
今天学了并查集,第一题练手!
这道题太可爱了! -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms#include
#define MAX 20001
int n,m,p;
int parent[MAX],rank[MAX];
void make_set(int i)
{
parent[i]=-1;
rank[i]=0;
}
int find(i)
{
if(parent[i]!=-1)
parent[i]=find(parent[i]);
if(parent[i]==-1)
return i;
else return parent[i];
}
void union_set(int i,int j)
{
int root1,root2;
root1=find(i);
root2=find(j);
if(root1!=root2)
{
if(rank[root1]>rank[root2])
parent[root2]=root1;
else{
parent[root1]=root2;
if(rank[root1]==rank[root2])
++rank[root2];
}
}
}
int main()
{int i,a,b,c,d;
scanf("%d %d %d",&n,&m,&p);
for(i=1;i -
0
code-geass LV 9 @ 2009-08-25 08:52:18
纯冰茶..........
-
0
var
c,d,n,m,p,i,j:longint;
a:array[1..5000]of longint;
begin
for i:=1 to 5000 do a[i]:=i;
readln(n,m,p);
for i:=1 to m do
begin
readln(c,d);
for j:=1 to n do if (a[j]=a[d])and(jd) then a[j]:=a[c];
a[d]:=a[c];
end;
for i:=1 to p do
begin
readln(c,d);
if a[c]=a[d] then writeln('Yes') else writeln('No');
end;
end. -
0
zhanghanyuan LV 10 @ 2009-08-10 15:03:21
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msMS
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
秒掉！
program p1034;
var
pa,a,b,c,d:array[1..5001] of longint;
a1,b1,p,i,j,k,l,e,w,q,s,z,xx,yy,x,y,max,min,m,n:longint;
function find(x:longint):longint;
var
i,j,k:longint;
begin
k:=x;
while xpa[x] do
x:=pa[x];
pa[k]:=x;
find:=x;
end;
procedure union(x,y:longint);
var
i,j,k:longint;
begin
if x -
0
var a,g:array[1..5000]of longint;
i,j,k,l,n,m,p,x,y:longint;
begin
read(n,m,p);
for i:=1 to n do a[i]:=i;
for i:=1 to m do
begin
read(x,y);k:=a[y];
for j:=1 to n do if a[j]=k then a[j]:=a[x];
end;
for i:=1 to p do
begin
read(x,y);
if a[x]=a[y] then g[i]:=1
else g[i]:=0;
end;
for i:=1 to p do if g[i]=1 then writeln('Yes')
else writeln('No');
end.
多么简洁啊 -
0
我们把一个连通块看作一个集合，问题就转化为判断两个元素是否属于同一个集合。假设一开始每个元素各自属于自己的一个集合，每次往图中加一条边a－b，就相当于合并了两个元素所在集合A和B，因为集合A中的元素用过边a－b可以到达集合B中的任意元素，反之亦然。当然如果a和b本来就已经属于同一个集合了，那么a-b这条边就可以不用加了。（1）具体操作：① 由此用某个元素所在树的根结点表示该元素所在的集合；② 判断两个元素时候属于同一个集合的时候，只需要判断他们所在树的根结点是否一样即可；③ 也就是说，当我们合并两个集合的时候，只需要在两个根结点之间连边即可。（2）元素的合并图示：（3）判断元素是否属于同一集合：用father[i]表示元素i的父亲结点，如刚才那个图所示：faher[1]:=1；faher[2]:=1；faher[3]:=1；faher[4]:=5；faher[5]:=3至此，我们用上述的算法已经解决了空间的问题，我们不再需要一个n2的空间来记录整张图的构造，只需要用一个记录数组记录每个结点属于的集合就可以了。但是仔细思考不难发现，每次询问两个元素是否属于同一个集合我们最多还是需要O(n)的判断！3. 算法3，并查集的路径压缩。算法2的做法是指就是将元素的父亲结点指来指去的在指，当这课树是链的时候，可见判断两个元素是否属于同一集合需要O(n)的时间，于是路径压缩产生了作用。路径压缩实际上是在找完根结点之后，在递归回来的时候顺便把路径上元素的父亲指针都指向根结点。这就是说，我们在“合并5和3”的时候，不是简单地将5的父亲指向3，而是直接指向根节点1，由此我们得到了一个复杂度只是O(1)的算法。
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msvar a:array[0..10000]of longint; m,i,t,fx,fy,n,x,y:longint;
function find(x:longint):longint;
begin
if x=a[x] then find:=a[x]
else find:=find(a[x]);
end;
begin
readln(n,m,t);
for i:=1 to n do
begin
a[i]:=i;
// dep[i]:=0;
end;
for i:=1 to m do
begin
readln(x,y);
fx:=find(x);
fy:=find(y);
a[fx]:=fy;
end;
for i:=1 to t do
begin
readln(x,y);
fx:=find(x);
fy:=find(y);
if fx=fy then writeln('Yes') else write('No');
end;
end.
无须优化,直接秒杀 -
0
var father,rank:array[1..10000]of longint;
x,y,t,tt,n,m,p,i:longint;
function find(x:longint):longint;
begin
if father[x]=x then exit(x);
father[x]:=find(father[x]);
exit(father[x]);
end;
begin
read(n,m,p);
for i:=1 to n do begin father[i]:=i;rank[i]:=1;end;
for i:=1 to m do
begin
read(x,y);
t:=find(x);tt:=find(y);
if rank[t]>rank[tt] then father[tt]:=t
else if rank[t] -
0
总以为错了，原来少打了 getfather(...)...
var
n,m,p,i,x,y:integer;
father:array[0..6000] of integer;
function getfather(i:integer):integer;
begin
if father[i]=i then exit(i)
else begin
father[i]:=getfather(father[i]);
exit(father[i]);
end;
end;
begin
readln(n,m,p);
for i:=1 to n do father[i]:=i;
for i:=1 to m do
begin
readln(x,y);
father[getfather(y)]:=getfather(x);
end;
for i:=1 to p do
begin
readln(x,y);
if getfather(father[x])=getfather(father[y]) then writeln('Yes')
else writeln('No');
end;
end. -
0
orz 终于会并查集了……
下个月再做一遍。#include
#includeint n,m,p;
int b[1000],f[6001]={0};void judge(int x,int y)
{
int fx,fy;
fx=getfather(x);
fy=getfather(y);
if(fx==fy) return;
else
f[fx]=fy;
}int getfather(int v)
{
if(f[v]==0)
{
return v;
}
else
{
f[v]=getfather(f[v]);
return f[v];
}
}int main()
{
int i,j,x,y,tmp;scanf("%d %d %d",&n,&m,&p);
for(i=1;i
mintalfance
LV 10
@ 2009-09-11 11:50:56
