Bài tập về đồ thị có hướng

[omakan]

Cho đồ thị có hướng (tối đa 500 đỉnh). tìm các đỉnh ít nhất để có thể đi hết đồ thị và cho biết là các đỉnh nào.

Rất mong mọi người giúp đỡ

[mr_invincible]

Không hiểu bạn định hỏi gì? Có phải là tìm số các đỉnh mà xuất phát từ đỉnh đó ta có thể đi hết đồ thị không? Nếu đúng thì có thể tìm kiếm theo chiều rộng

[vuacuagai]

cái này sao giống chu trình haminton quá, hổng biết có đúng hông nữa
http://laptopforstudent.googlepages.com/vpo160x60_2.gif (http://vpsion.org)

[omakan]

đúng là tìm số các đỉnh (ít nhất) có thể đi hết đồ thị. bạn nói rõ về thuật toán được không?

[mr_invincible]

Tôi không hiểu từ ít nhất là gì? Và cũng không hiểu khái niệm đi hết đồ thị của bạn là như thế nào? Nghĩa là đi từ một đỉnh đến lần lượt các đỉnh khác hay từ một đỉnh có thể đi đến đỉnh bất kì (2 vấn đề này hoàn toàn khác nhau) và có cần đi hết tât cả các cạnh không?
Theo tôi, bạn phải viết thật cụ thể, rõ nghĩa đề bài ra thì mọi người mới có thể giúp được. Tốt nhất cho luôn cả một vài ví dụ để thêm phần dễ hiểu

[Master_Baby]

- to mr_invincible
Một đồ thị gồm n đỉnh, m cung, mỗi cung bắt đầu từ một đỉnh và kết thúc tại một đỉnh (gốc và ngọn, có trường hợp gốc và ngọn trùng nhau) Đồ thị có hướng tức mỗi cung đều có hướng, chỉ có thể đi từ gốc đến ngọn của cung muh thôi. (Đồ thị vô hướng có thể đi 2 chiều)
- nói thật tui cũng hông hiểu đề bài :P

[omakan]

đại loại đề nó như thế này:
Cho đồ thị có hướng (Từ đỉnh A có thể sang đỉnh B nhưng chưa chắc từ đỉnh B có thể sang đỉnh A), nếu xuất phát từ một đỉnh chưa chắc có thể duyệt hết được đồ thị (đi hết đồ thị). Do đó đề bài yêu cầu tìm số đỉnh ít nhất để có thể duyệt hết đồ thị
vd: cho input gồm 5 đỉnh:
5 (số đỉnh)
1 2 (liên kết 1 chiều từ đỉnh 1 đến đỉnh 2)
1 4
1 5
3 2
3 5

trường hợp này cần xuất phát từ đỉnh 1 và đỉnh 3 mới có thể duyệt hết đồ thị. Nếu sửa input đoạn "3 2" thành "2 3" thì chỉ cần xuất phát từ đỉnh 1 là có thể duyệt hết đồ thị

[mr_invincible]

Vậy là bài về đồ thị liên thông hả? Nhưng còn yêu cầu thêm là cần phải sửa cạnh để đi hết đồ thị với số đỉnh ít nhất hả? Nhưng có thể thay đổi cạnh ntn? Có thể đổi chiều cạnh hả? Có thể thêm cạnh không? Có thể làm gì khác nữa không?

[omakan]

không thể làm ji` khác được, input đã cho rồi thì không thể sửa cạnh được :D, cái sửa cạnh lúc nãy như là ví dụ thứ hai vậy thôi

[jiSh@n]

đại loại đề nó như thế này:
Cho đồ thị có hướng (Từ đỉnh A có thể sang đỉnh B nhưng chưa chắc từ đỉnh B có thể sang đỉnh A), nếu xuất phát từ một đỉnh chưa chắc có thể duyệt hết được đồ thị (đi hết đồ thị). Do đó đề bài yêu cầu tìm số đỉnh ít nhất để có thể duyệt hết đồ thị
vd: cho input gồm 5 đỉnh:
5 (số đỉnh)
1 2 (liên kết 1 chiều từ đỉnh 1 đến đỉnh 2)
1 4
1 5
3 2
3 5

trường hợp này cần xuất phát từ đỉnh 1 và đỉnh 3 mới có thể duyệt hết đồ thị. Nếu sửa input đoạn "3 2" thành "2 3" thì chỉ cần xuất phát từ đỉnh 1 là có thể duyệt hết đồ thị

số đỉnh ít nhất <<< giải thích chỗ này xem, ví dụ ko thấy:)

[omakan]

có thể duyệt hết đồ thị trong input trên bằng cách xuất phát từ cả 5 đỉnh. Nhưng chỉ cần xuất phát từ đỉnh 1 và 3 là có thể duyệt hết đồ thị rồi. và trong input này thì 2 đỉnh là số đỉnh ít nhất cần đề duyệt đồ thị

[mr_invincible]

À nói tóm lại là tìm số đỉnh ít nhất cần có để đi hết đồ thị chứ gì. Vậy mà bạn còn thêm phần sửa input vào làm gì.
Thuật toán:
Chừng nào các đỉnh còn chưa được đánh dấu hết thì còn
Tăng số đỉnh ít nhất
Bắt đầu từ đầu tiên chưa được xét dùng phương pháp duyệt theo chiều rộng để tìm tất cả các đỉnh có thể đi đến và đánh dấu các đỉnh này.
Hết vòng lặp

[omakan]

hì hì, vấn đề đây là đồ thị có hướng :D

[mr_invincible]

Đồ thị có hướng thì có khác gì đâu? Cứ duyệt theo chiều rộng, nhưng nếu không đến được đỉnh đó thì thôi?
Bạn có thể giải thích kĩ hơn không?

[F12]

Thuật toán:
Chừng nào các đỉnh còn chưa được đánh dấu hết thì còn
Tăng số đỉnh ít nhất
Bắt đầu từ đầu tiên chưa được xét dùng phương pháp duyệt theo chiều rộng để tìm tất cả các đỉnh có thể đi đến và đánh dấu các đỉnh này.
Hết vòng lặp
Ví dụ test này :
3 --> 2 --> 1
Theo thuật toán của bạn: ban đầu bfs(1), rồi bfs(2), rồi bfs(3). Kết quả thu được là 3.
Nhưng đáp số là 1. Chỉ cần bfs(3) thôi.
Vậy thuật toán của bạn sai.

[jiSh@n]

có thể duyệt hết đồ thị trong input trên bằng cách xuất phát từ cả 5 đỉnh. Nhưng chỉ cần xuất phát từ đỉnh 1 và 3 là có thể duyệt hết đồ thị rồi. và trong input này thì 2 đỉnh là số đỉnh ít nhất cần đề duyệt đồ thị

Bạn duyệt kiểu gì thế? Nếu xuất phát từ đỉnh 1 thì bạn chỉ có thể chọn 1 trong 3 đường 1->2, 1->4, 1->5 chứ ko thể nào chọn cùng lúc cả 3 đường được. Giả sử bạn chọn 1->2 thì bạn chỉ còn có 3->5 và 4 thôi (do từ 1->2 sẽ ko còn đường nào quay về 1 để đi theo 1->4...), như vậy nghiệm phải là 3 đỉnh (1,3,4).

Còn nếu như bạn chọn 1->2 rồi tiếp tục chọn 1->4,... thì tập nghiệm thực tế sẽ phải là (1,1,3) hoặc (1,1,1,3), và đây là lần đầu tiên tôi biết đến 1 cách duyệt đồ thị hữu hướng như thế ;)

[omakan]

Hic, thôi thì post luôn nguyên cái đề vậy, dù ji` cũng hết hạn nộp bài rồi =.=''.
Một lớp gồm N học sinh. Mỗi học sinh cho biết những bạn mà học sinh đó có thể liên lạc được (liên lạc 1 chiều: A liên lạc dc với B nhưng chưa chắc B liên lạc được với A). Thầy giáo có thông tin cần báo với tất cả học sinh. Để tiết kiệm thời gian. thầy chỉ nhắn tới 1 số học sinh rồi sau đó nhờ các học sinh này nhắn cho các bạn mà các học sinh đó có thể liên lạc được. Cứ thế sao cho tất cả học sinh đều nhận được tin.
input dòng đầu là số N. Các dòng tiếp theo gồm 2 số A và B cho biết học sinh A có thể liên lạc được với học sinh B

[phuclun]

bài này có trên vn.spoj.pl nàh,thầy cho bạn bài này hả.