1 条题解

  • 0
    @ 2023-3-13 12:11:09

    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
    上传者