BCDAISY spoj PTIT – Chú bò hư hỏng
Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCDAISY/ 1. Đề bài BCDAISY spoj Nông dân John có N (1<=N<=250) con bò đánh số từ 1..N chơi trên bãi cỏ. Để tránh bị lạc mất các con bò, mỗi con bò có thể được nối với một số con bò khác bằng dây thừng. Có tất cả M (1 <= M ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCDAISY/
1. Đề bài BCDAISY spoj
Nông dân John có N (1<=N<=250) con bò đánh số từ 1..N chơi trên bãi cỏ.
Để tránh bị lạc mất các con bò, mỗi con bò có thể được nối với một số con bò khác bằng dây thừng.
Có tất cả M (1 <= M <= N*(N-1)/2) dây thừng nối các con bò. Tất nhiên, không có 2 con bò mà có nhiều
hơn 1 dây thừng nối giữa chúng. Dữ liệu cho biết mỗi cặp con bò c1 và c2 là nối với nhau (1 <= c1 <= N; 1 <= c2 <= N; c1 != c2).
Nông dân John buộc cố định con bò 1 bằng sợi dây xích. Các con bò khác phải nối với con bò 1 bằng một số sợi dây thừng. Tuy nhiên, một số con bò hư hỏng không như vậy. Hãy giúp nông dân John tìm các con bò hư hỏng đó (không kết nối tới bò 1). Dĩ nhiên, con bò thứ 1 luôn nối tới chính nó.
INPUT:
* Dòng 1: 2 số nguyên cách nhau bởi dấu cách: N and M
* Lines 2..M+1: Dòng i+1 cho biết 2 con bò nối với nhau bằng sợi dây thứ i là c1 và c2 cách nhau bởi dấu cách.
OUTPUT FORMAT:
* Nếu không có con bò hư hỏng, in ra 0.
* Ngược lại, in ra trên mỗi dòng 1 số nguyên là thứ tự con bò hư hỏng theo thứ tự tăng dần.
SAMPLE INPUT:
6 4
1 3
2 3
1 2
4 5
SAMPLE OUTPUT:
4
5
6
Giải thích:
Input có thể mô tả như hình dưới đây:
1—2 4—5
|
| 6
|
3
Dễ thấy, các con bò 4, 5, và 6 không nối tới con bò 1.
2. Hướng dẫn BCDAISY spoj PTIT
– đây là dạng bài toán Liên thông , các bạn có thể áp dụng BFS, DFS hoặc tư tưởng của Kruskal đều được.
Tuy nhiên có thể nói tư tưởng Kruskal là có tốc độ hiệu quả nhất.
3. Code tham khảo BCDAISY spoj PTIT (BFS, DFS, Kruskal)
a. Code BFS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | const fi = '; fo = '; var n, i, m, u, v : integer; a : array[1..250,1..250] of 0..1; q : array[1..250] of integer; free : array[1..250] of boolean; ok : boolean; procedure bfs(u:integer); var first, last, v : integer; begin first:=1; last:=1; q[first]:=u; free[u]:=false; repeat u:=q[first]; inc(first); for v:=1 to n do if free[v] and (a[u,v]=1) then begin inc(last); q[last]:=v; free[v]:=false; end; until first > last; end; begin assign(input,fi);reset(input); assign(output,fo);rewrite(output); readln(n,m); ; fillchar(a,sizeof(a),0); fillchar(free,sizeof(free),true); for i:=1 to m do begin readln(u,v); a[u,v]:=1; a[v,u]:=1; end; bfs(1); ok:=false; for i:=1 to n do if free[i] then begin writeln(i);ok:=true;end; if not ok then writeln(0); close(input);close(output); end. |
b. Code DFS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | const fi = '; fo = '; var n, m, i : longint; free : array[1..5000] of boolean; a : array[1..5000,1..5000] of 0..1; ok : boolean; procedure Enter; var u, v, i, j : longint; begin readln(n,m); fillchar(a,sizeof(a),0); fillchar(free,sizeof(free),true); for i:=1 to m do begin readln(u,v); a[u,v]:=1; a[v,u]:=1; end; end; procedure Dfs(u:longint); var v, i :longint; begin free[u]:=false; for v:=1 to n do if (free[v]=true) and (a[u,v]=1) then Dfs(v); end; begin assign(input,fi);reset(input); assign(output,fo);rewrite(output); Enter; //for i:=1 to n do dfs(1); ok:=false; for i:=1 to n do if free[i] then begin writeln(i);ok:=true;end; if not ok then writeln(0); close(input);close(output); end. |
c. Code Kruskal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | const fi='; nmax=250; type data=longint; var f:text; root:array[0..nmax+1] of data; n,m:data; procedure union(a,b:data); begin if a>b then root[a]:=b else root[b]:=a; end; function findroot(x:data):data; begin if root[x]<>x then root[x]:=findroot(root[x]); exit(root[x]); end; procedure docfile; var i,j,u,v,c,ur,uv:data; begin assign(f,fi); reset(f); readln(f,n,m); for i:=1 to n do root[i]:=i; for i:=1 to m do begin readln(f,u,v); ur:=findroot(u); uv:=findroot(v); if ur<>uv then union(ur,uv); end; close(f); end; procedure xuli; var i,j,dem:data; begin dem:=0; for i:= 2 to n do if findroot(i)<>1 then begin writeln(i); inc(dem); end; if dem=0 then writeln(0); end; begin docfile; xuli; end. |
