SPOJ.com - Problem BCDAISY

Problem hidden

|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BCDAISY - Chú bò hư hỏng

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.

ID	RESULT	TIME

code...

Submit solution!

Được gửi lên bởi:	adm
Ngày:	2011-11-07
Thời gian chạy:	0.200s
Giới hạn mã nguồn:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Ngôn ngữ cho phép:	ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments



2024-08-12 20:51:04 int n, m; vi d(251, 0), v(251, 0), p(251, -1); void bfs(vector<vi>& g) { queue<int> q; q.push(1); v[1] = 1; while(!q.empty()) { int u = q.front(); q.pop(); ff(i, g[u]) { if (!v[i]) { p[i] = u; d[i] = d[u] + 1; v[i] = 1; q.push(i); } } } } void f11() { cin >> n >> m; vector<vi> g(n + 1); f0(i, m) { int x, y; cin >> x >> y; g[x].pb(y); g[y].pb(x); } bfs(g); // ff(i, d) cout << i << el; bool ok = 0; for(int i = 1; i <= n; i++) { if (!v[i]) { cout << i << el; ok = 1; } } if (ok==0) cout << 0 << el; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed << setprecision(2); f11(); }
2024-01-06 11:58:55 cứu em với các cao nhân ơi, em mới được có 60 điểm thui à, có ràng buộc gì để full ko ạ!
2022-03-28 18:26:15 . Last edit: 2022-03-29 03:53:35
2020-02-07 08:53:36 "Nếu không có con bò hư hỏng, in ra 0." meow meow~ Chú Mèo Chui Xoong: meow
2018-11-15 22:51:24 Basic DFS.
2018-10-11 14:28:18 DSU
2018-05-17 03:01:11 ae giúp cái mới đc 20/100
2017-08-21 09:47:50 Ðặng Minh Tiến https://kienthuc24h.com/bcdaisy-spoj-ptit-chu-bo-hu-hong/
2017-07-14 10:21:46 BCDAISY: https://e16cn-ptit.blogspot.com/2017/12/bcdaisy-chu-bo-hu-hong.html Last edit: 2017-12-08 06:12:51
2017-06-17 04:15:07 First Command

Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

BCDAISY - Chú bò hư hỏng