1 solutions

  • 0
    @ 2024-12-10 22:28:05

    C++ :

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    
    struct E
    {
    	int y,next;
    }e[200001];
    int g[100001],n,m,tmp,sum;
    int q[2][100001],o;
    bool ill[100001],mian[100001];
    
    int main()
    {
    	scanf("%d%d",&n,&m);
    	int x,y;
    	for (int i=1;i<=m;i++)
    	{
    		scanf("%d%d",&x,&y);
    		e[++tmp].y=y;
    		e[tmp].next=g[x];
    		g[x]=tmp;
    		e[++tmp].y=x;
    		e[tmp].next=g[y];
    		g[y]=tmp;
    	}
    	
    	int a;
    	scanf("%d",&a);
    	q[o][++q[o][0]]=a;
    	ill[a]=true;
    	
    	while (q[o][0])
    	{
    		sum++;
    		if (sum>100000000)
    		{
    			printf("-1");
    			return 0;
    		}
    		for (int i=1;i<=q[o][0];i++)
    		{
    			int now=q[o][i];
    			int fri,fr=g[now];
    			while (fr)
    			{
    				fri=e[fr].y;
    				if ((!ill[fri])&&(!mian[fri]))
    				{
    					q[!o][++q[!o][0]]=fri;
    					ill[fri]=true;
    				}
    				fr=e[fr].next;
    			}
    		}
    		memset(mian,0,sizeof(mian));
    		for (int i=1;i<=q[o][0];i++)
    		{
    			ill[q[o][i]]=false;
    			mian[q[o][i]]=true;
    		}
    		memset(q[o],0,sizeof(q[o]));
    		o=!o;
    	}
    	
    	printf("%d",sum);
    	return 0;
    }
    

    Pascal :

    type
       pointer=^rec1;
       rec1=record
             value:longint;
             next:pointer;
           end;
    
       rec2=record
              node,step:longint;
            end;
    
    var
       connect:array[1..100000]of pointer;
       queue:array[1..100000]of rec2;
       hash:array[1..100000]of boolean;
       n,m,t:longint;
    
    procedure insert(x,y:longint);
    var
       tmp:pointer;
    begin
       new(tmp);
       tmp^.value:=x;
       tmp^.next:=connect[y];
       connect[y]:=tmp;
    end;
    
    procedure readp;
    var
       i,x,y:longint;
    begin
       readln(n,m);
       for i:=1 to m do
       begin
          readln(x,y);
          insert(x,y);
          insert(y,x);
       end;
       readln(t);
    end;
    
    procedure solve;
    var
       closed,open:longint;
       tmp:pointer;
    begin
       closed:=0;
       open:=1;
       queue[1].node:=t;
       queue[1].step:=1;
       hash[t]:=true;
    
       repeat
          closed:=closed+1;
          tmp:=connect[queue[closed].node];
          while tmp<>nil do
          begin
             if not hash[tmp^.value] then
             begin
                hash[tmp^.value]:=true;
                open:=open+1;
                queue[open].node:=tmp^.value;
                queue[open].step:=queue[closed].step+1;
             end;
             tmp:=tmp^.next;
          end;
       until closed>=open;
    
       writeln(queue[open].step);
    end;
    
    begin
       
       readp;
       solve;
       
    end.
    
    • 1

    Information

    ID
    551
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By