查看题目 Show Problem
题目:相连的农场
问题编号:480 [提交该题] [讨论该问题] [有关讨论] [Who AC] [相关题解] [最优解]
My Flag:Unsubmited
题目类型
图结构
描述
Farmer John的农场被一次意外事故破坏了，有一些农场与其他的农场之间有道路相连，而有些道路却已被破坏。这使得Farmer John 无法了解到从一个农场能否到达另一个农场。你的任务就是帮助Farmer John来了解哪些农场是连通的。
给出一个无权图，请你按顺序输出图中所有的连通块。
输入格式
第一行是点数n(1<=n<=500)，以下n行为这个图的邻接矩阵。
输出格式
第一行是连通块的个数m，以下m行，每一行是一个连通块中农场的序号，末尾有一空格。
注意，输出时，每个连通块中的点按点序号的大小顺序输出，而个个连通块按连通块中的第一个点的顺序输出。
样例输入
5
0 1 0 1 0
1 0 0 0 0
0 0 0 0 1
1 0 0 0 0
0 0 1 0 0
样例输出
2
1 2 4
3 5
*/
#include<iostream>
using namespace std；
int father[501],n,m；
int road[501][501]；
struct block
{
int num,father；
int ns[501]；
} bs[501]；
void initialize(){
scanf("%d",&n)；
for (int i=1；i<=n；++i)
father[i]=i；
for (int i=1；i<=n；++i)
for (int j=1；j<=n；++j)
scanf("%d",&road[i][j])；
}
int getfather(int v){
if (father[v]==v) return v；
return father[v]=v；
}
void join(int v1,int v2){
int f1,f2；
f1=getfather(v1)；
f2=getfather(v2)；
father[f1]=f2；
}
int cmp(const void *a,const void *b){
return *(int *)a-*(int *)b；
}
int cmp1(const void *a,const void *b){
return (*(block *)a).ns[0]-(*(block *)b).ns[0]；
}
void measure(){
for (int i=1；i<=n；++i)
for (int j=1；j<=n；++j)
if (road[i][j]==1) join(i,j)；
m=0；
for (int i=1；i<=n；++i)
if (father[i]==i){
bs[m].num=0；
bs[m].father=i；
++m；
}
for (int i=1；i<=n；++i)
for (int j=0；j<m；++j)
if (bs[j].father==father[i])
bs[j].ns[bs[j].num++]=i；
for (int j=0；j<m；++j)
qsort(bs[j].ns,bs[j].num,sizeof(bs[j].ns[0]),cmp)；
qsort(bs,m,sizeof(bs[0]),cmp1)；
}
void output(){
int j；
cout<<m；
for (j=0；j<m-1；++j){
cout<<endl；
for (int k=0；k<bs[j].num；++k)
cout<<bs[j].ns[k]<<’ ’；
}
cout<<endl；
for (int k=0；k<bs[j].num；++k){
if (k!=0) cout<<’ ’；
cout<<bs[j].ns[k]；
}
}
int main (void){
initialize()；
measure()；
output()；
while (1)；
return 0；
}
program sdf；
var
i,j,k,m,n,l,t:longint；
a:array[0..500,0..500] of integer；
c:array[1..500] of longint；
v:array[1..500] of boolean；
procedure dfs(x:integer)；
var
i,j:integer；
begin
c[x]:=m；
v[x]:=true；
for i:=1 to n do
if (not v[i]) and(a[x,i]=1) then dfs(i)；
end；
begin
readln(n)；
for i:=1 to n do
for j:=1 to n do begin
read(a[i,j])；
a[j,i]:=a[i,j]；
end；
m:=0；
for i:=1 to n do
if not v[i] then begin inc(m)；dfs(i)；end；
writeln(m)；
for i:=1 to m do begin
for j:=1 to n do
if c[j]=i then write(j,’ ’)；
writeln；
end；
end.
LZ是怎么个意思啊,并查集怎么做啊？
program sdf；
var
i,j,k,m,n,l,t:longint；
a:array[0..500,0..500] of integer；
c:array[1..500] of longint；
v:array[1..500] of boolean；
procedure dfs(x:integer)；
var
i,j:integer；
begin
c[x]:=m；
v[x]:=true；
for i:=1 to n do
if (not v[i]) and(a[x,i]=1) then dfs(i)；
end；
begin
readln(n)；
for i:=1 to n do
for j:=1 to n do begin
read(a[i,j])；
a[j,i]:=a[i,j]；
end；
m:=0；
for i:=1 to n do
if not v[i] then begin inc(m)；dfs(i)；end；
writeln(m)；
for i:=1 to m do begin
for j:=1 to n do
if c[j]=i then write(j,’ ’)；
writeln；
end；
end.
LZ是怎么个意思啊,并查集怎么做啊？
program sdf；
var
i,j,k,m,n,l,t:longint；
a:array[0..500,0..500] of integer；
c:array[1..500] of longint；
v:array[1..500] of boolean；
procedure dfs(x:integer)；
var
i,j:integer；
begin
c[x]:=m；
v[x]:=true；
for i:=1 to n do
if (not v[i]) and(a[x,i]=1) then dfs(i)；
end；
begin
readln(n)；
for i:=1 to n do
for j:=1 to n do begin
read(a[i,j])；
a[j,i]:=a[i,j]；
end；
m:=0；
for i:=1 to n do
if not v[i] then begin inc(m)；dfs(i)；end；
writeln(m)；
for i:=1 to m do begin
for j:=1 to n do
if c[j]=i then write(j,’ ’)；
writeln；
end；
end.
LZ是怎么个意思啊,并查集怎么做啊？
program sdf；
var
i,j,k,m,n,l,t:longint；
a:array[0..500,0..500] of integer；
c:array[1..500] of longint；
v:array[1..500] of boolean；
procedure dfs(x:integer)；
var
i,j:integer；
begin
c[x]:=m；
v[x]:=true；
for i:=1 to n do
if (not v[i]) and(a[x,i]=1) then dfs(i)；
end；
begin
readln(n)；
for i:=1 to n do
for j:=1 to n do begin
read(a[i,j])；
a[j,i]:=a[i,j]；
end；
m:=0；
for i:=1 to n do
if not v[i] then begin inc(m)；dfs(i)；end；
writeln(m)；
for i:=1 to m do begin
for j:=1 to n do
if c[j]=i then write(j,’ ’)；
writeln；
end；
end.
LZ是怎么个意思啊,并查集怎么做啊？
for (int i=1；i<=n；++i)
for (int j=1；j<=n；++j)
if (road[i][j]==1) join(i,j)；
这句+join函数的构造过程应该会出事
你并查集没有构造好