n,i,m,j,x,y,t,tot:longint;
ch,cc:char;
a:array [0..1000] of integer;
b:array [1..5000,1..2] of integer;
c:array [0..1000] of boolean;
function find(v:longint):longint;
begin
if a[v]=v then exit(v)
else
begin
a[v]:=find(a[v]);
find:=a[v];
end;
end;
begin
readln(n);
readln(m);
t:=0;
fillchar(c,sizeof(c),true);
for i:=1 to n do a[i]:=i;
for i:=1 to m do
begin
readln(ch,cc,x,y);
if ch='F' then a[find(a[x])]:=find(a[y]);
if ch='E' then
begin
inc(t);
b[t,1]:=x; b[t,2]:=y;
end;
end;
for i:=1 to t do
for j:=i+1 to t do
begin
if b[i,1]=b[j,1] then a[find(a[b[i,2]])]:=a[b[j,2]];
if b[i,1]=b[j,2] then a[find(a[b[i,2]])]:=a[b[j,1]];
if b[i,2]=b[j,1] then a[find(a[b[i,1]])]:=a[b[j,2]];
if b[i,2]=b[j,2] then a[find(a[b[i,1]])]:=a[b[j,1]];
end;
for i:=1 to n do
a[i]:=find(a[i]);
tot:=0;
for i:=1 to n do
if c[a[i]] then
begin
inc(tot);
c[a[i]]:=false;
end;
writeln(tot);
end.
答案绝对正确
就是一直溢出
求大牛们如何改进
楼主的程序function的find是并查集的路径压缩么？
应该是那里的问题。楼主可以尝试手工建栈。
贴个C++的
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
#define MAX_N 1001
int f[MAX_N], e[MAX_N];
int n, m, ans;
int find(int x)
{
if (f[x]) return f[x] = find (f[x]);
else return x;
}
void union_set(int a, int b)
{
a = find (a), b = find (b);
if (a != b) f[a] = b;
}
int main(void)
{
scanf ("%d%d", &n, &m);
for (int i = 1, a, b; i <= m; i++)
{
char c[2];
scanf ("%s%d%d", &c, &a, &b);
if (c[0] == 'F') union_set (a, b);
else if (c[0] == 'E')
{
if (e[a] == 0) e[a] = b;
else union_set (e[a], b);
if (e[b] == 0) e[b] = a;
else union_set (e[b], a);
}
}
for (int i = 1; i <= n; i++)
if (!f[i]) ans++;
printf ("%d", ans);
return 0;
}