Страница 2 WA8 Please, explain, what is the reason? Is this just a problem of input/output or this is just such test case? I found the problem, wrong algorithm. So, we can decompose like this any connected graph G = (V, E), |E| = 2k, k in Z+? This is lovely, this is nice (I proved it using induction, I'm proud of myself, yay!). I came up to this idea, but failed to proof. Could anyone help me? In general this task is quite hard to make bugs if you know what to do... What is your approach? Posting code is not a nice idea. Moreover it is not ideal. My mistake was usage of queue when the correct is using a stack. Only changed that, and then got AC 0.015 sec 480 KB. I'm so happy :D Edited by author 05.08.2015 05:31 It's very simple problem because all connected graphs which containes even number of edges can be divided into pairs of edges, which includes one common vertex!!!(and all connected graphs with odd number of edges can't be divided in such way) input 5 4 4 2 2 1 1 3 3 4 I think output should "1" but most of my colleagues' accepted programs print "0". Do I misunderstand the problem ? This is not valid input because the graph has to have an even number of edges. CONGRATULATIONS TO THE AUTHOR!!!!! who can help me? I WA on #7.Why? here is my program: var a:array[1..1000]of longint; b:array[1..1000,1..1000]of boolean; n,i,j,x,y,m:longint; c:boolean; function find(x,y:longint):boolean; var i:longint; begin if b[x,y] then exit(false); for i:=1 to m do if (b[a[i],x])and(b[a[i],y])then begin b[x,y]:=true;b[y,x]:=true; exit(false); end; exit(true); end; begin while not seekeof do begin readln(x,y); b[x,x]:=true;b[y,y]:=true; b[x,y]:=true;b[y,x]:=true; c:=true; for j:=1 to m do if a[m]=x then begin c:=false;break;end; if c then begin inc(m);a[m]:=x; for i:=1 to m do if find(a[i],x) then begin writeln(0);halt; end; end; c:=true; for j:=1 to m do if a[m]=y then begin c:=false;break;end; if c then begin inc(m);a[m]:=y; for i:=1 to m do if find(a[i],y) then begin writeln(0);halt; end; end; end; writeln(1); end. Pls check for the following case: 5 6 5 8 5 9 6 7 8 9 9 10 Answer should be 1 Test 7 has invert vertexes. 10 1 1 2 asn: 1 I have many times WA, because my programm doesnt check it. Страница 1 1 2 2 3 3 1 1 10 in this test , i do not know why ? what about the others vertex ? 4,5,6,7,8,9 ?? "Imagine graph drawn on a wall. Select any vertex and erase exactly two edges incidental to this vertex. The question of problem is: "Is it possible to erase all edges of graph doing in this way?"" think again: 1 2 2 3 3 1 1 10 you will understand.... void Readinp() { int x,y; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); while (cin >> x >>y) { a[x][y]=1; a[y][x]=1; b[x]++; b[y]++; n=max(n,max(x,y)); } } begin randomize; writeln(random(2)); end. Who can AC by this program??? =) if you are lucky enough Edited by author 25.12.2008 02:46 Could anyone help me? I find mistake in my source code. I got AC in pascal it is 'seekeof()', and in C++ ? Is test1 the sample? I have WA#1 !!! input 1 2 2 3 3 1 1 10 output 0 Can i write "1" if all connected components of graph have even number of edges? |
|