Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
GRAPH_ - Tìm khớp và cầu (Cơ bản) |
Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/graph_
Xét đơn đồ thị vô hướng G = (V, E) có n(1<=n<=10000) đỉnh và m(1<=m<=50000) cạnh. Người ta định nghĩa một đỉnh gọi là khớp nếu như xoá đỉnh đó sẽ làm tăng số thành phần liên thông của đồ thị. Tương tự như vậy, một cạnh được gọi là cầu nếu xoá cạnh đó sẽ làm tăng số thành phần liên thông của đồ thị.
Vấn đề đặt ra là cần phải đếm tất cả các khớp và cầu của đồ thị G.
Input
+Dòng đầu: chứa hai số tự nhiên n,m.
+M dòng sau mỗi dòng chứa một cặp số (u,v) (u<>v, 1<=u<=n, 1<=v Gồm một dòng duy nhất ghi hai số, số thứ nhất là số khớp, số thứ hai là số cầu của GOutput
Example
Input:
10 12
1 10
10 2
10 3
2 4
4 5
5 2
3 6
6 7
7 3
7 8
8 9
9 7
Output:
4 3
Được gửi lên bởi: | Phan Công Minh |
Ngày: | 2010-03-09 |
Thời gian chạy: | 0.100s |
Giới hạn mã nguồn: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Ngôn ngữ cho phép: | Tất cả ngoại trừ: GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET |
Nguồn bài: | Bài cổ điển - tests added by canhteo |
hide comments
|
||||||||
2013-04-01 04:28:56 Ngô Huỳnh Ngọc Khánh♥(TN)♥
DFS? |
||||||||
2011-07-06 13:02:37 up!
pointer Last edit: 2011-07-06 13:02:57 |
||||||||
2010-11-23 09:31:13 Hoàng Hà
Cơ bản |
||||||||
2010-10-16 16:44:33 phúc
ai có test nào post lên cho em thử với, sao chạy test trong vd đúng mà chấm đc 0 nhỉ |
||||||||
2010-07-15 15:17:51 Tâm Chớp Nhoáng
đi mà hỏi Mao chủ tịch :D |
||||||||
2010-07-04 15:46:59 dhkhtn
sao ko tang no len thanh 1s nhi? |