1 solutions
-
0
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