1 条题解
-
0
C++ :
#include<iostream> #include<cstring> #include<queue> #include<cstdio> using namespace std; bool a[110][110]; bool flag[110]; int n,e; void init(); void bfs(int x); int main() { //freopen("bfs5.in","r",stdin); //freopen("bfs5.out","w",stdout); init(); bfs(1); return 0; } void init() { cin>>n>>e; memset(flag,0,sizeof(flag)); memset(a,0,sizeof(a)); int x,y; for(int i=1;i<=e;++i) { cin>>x>>y; a[x][y]=1;//无向图处理双向 a[y][x]=1; } } void bfs(int x) { queue<int> q; cout<<x<<' '; flag[x]=1;//把遍历点设为已访问 q.push(x);//把当前点进队 while(!q.empty())//当队列非空 { for(int i=1;i<=n;i++) { if(!flag[i]&&a[q.front()][i])//遍历队首元素的相邻点 { cout<<i<<' ';//如果连通且没访问过进队 flag[i]=1;//一定要记得设访问标记,否会是死循环 q.push(i); } } q.pop(); } }
Pascal :
program acm21183; const maxn=100; type node=record u,v,next:longint; end; var q:array[1..10000] of longint; num,i,j,k,n,e,u,v,x:longint; graph:array[1..maxn,1..maxn] of longint; vis:array[1..maxn] of boolean; procedure bfs; var i,f,r:longint; begin f:=0; r:=1; q[1]:=1; vis[1]:=true; while f<r do begin inc(f); x:=q[f]; if k=0 then begin write(x); k:=k+1 end else write(' ',x); for i:=1 to n do if (not vis[i]) and (graph[x,i]>0) then begin graph[x,i]:=0; graph[i,x]:=0; vis[i]:=true; inc(r); q[r]:=i; end; end; end; procedure init; var i:longint; begin fillchar(graph,sizeof(graph),0); readln(n,e); for i:=1 to e do begin readln(u,v); graph[u,v]:=1; graph[v,u]:=1; end; end; begin fillchar(vis,sizeof(vis),0); init; k:=0; bfs; end.
- 1
信息
- ID
- 2108
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 5
- 已通过
- 1
- 上传者