Tìm khớp và cầu (Cơ bản)

Điểm: 0,14 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

Bài cổ điển - tests added by canhteo

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Xét đơn đồ thị vô hướng ~G =~ ~(V~, ~E)~ có ~N~ ~(1 \le N \le 10000)~ đỉnh và ~M~ ~(1 \le M \le 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~ khác ~v~, ~1 \le u \le N~, ~1 \le v < N)~ mô tả một cạnh của ~G~.

Output

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 ~G~

Sample Input

Sample Output

4 3

Note

Bình luận

Hãy đọc nội quy trước khi bình luận.

0

hoangquys đã bình luận lúc 29, Tháng 12, 2025, 15:03

2 test cuối duyệt brute force bình thường

vominhmanh10 đã bình luận lúc 1, Tháng 11, 2025, 8:00 ← sửa 2 →

lỗi value error do vấn đề đọc input, hãy đọc toàn bộ trước và lưu từng phần

import sys

def dfs(u, par):
    global timer, canh_cau
    tin[u] = low[u] = timer
    timer += 1
    child = 0
    for v in adj[u]:
        if v == par:
            continue
        if tin[v] == 0:
            dfs(v, u)
            low[u] = min(low[u], low[v])
            if low[v] > tin[u]:
                canh_cau += 1
            child += 1
            if par == -1:
                if child > 1:
                    khop.add(u)
            else:
                if low[v] >= tin[u]:
                    khop.add(u)
        else:
            low[u] = min(low[u], tin[v])

input = sys.stdin.readline
sys.setrecursionlimit(10**7)
data = sys.stdin.read().strip().split()
n, m = map(int, data[0:2])
adj = [[] for _ in range(n + 1)]
for i in range(2, 2 * m + 2, 2):
    u, v = int(data[i]), int(data[i + 1])
    adj[u].append(v)
    adj[v].append(u)
tin = [0] * (n + 1)
low = [0] * (n + 1)
timer = 1
khop = set()
canh_cau = 0
for i in range(1, n + 1):
    if tin[i] == 0:
        dfs(i, -1)
print(len(khop), canh_cau)

-6

yureki3657 đã bình luận lúc 31, Tháng 8, 2025, 10:22

imgay

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

1

tadanhdat123 đã bình luận lúc 9, Tháng 8, 2025, 5:52 ← chỉnh sửa →

Input của bài có trường hợp một đồ thị không liên thông

1

pppssslc đã bình luận lúc 9, Tháng 8, 2025, 6:57 ← chỉnh sửa →

Đề bài cho đây là đơn đồ thị vô hướng rồi mà. Bạn đọc kĩ lại đề bài nha.

2

tadanhdat123 đã bình luận lúc 9, Tháng 8, 2025, 8:40 ← sửa 2 →

Cảm ơn bạn nhìu nha, mình có lưu ý chỗ đó rồi á ( trùng với tất cả các điều kiện của bài trên ) . Nhưng bài này có nhiều bản sao, mình nộp bên OJ khác thì bị sai 2 trường hợp trên. Mình chỉ không hiểu chỗ đó thui bạn.

-7

LVT_K66_TRANDUYBAO đã bình luận lúc 26, Tháng 7, 2025, 1:55

xin dowvote

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-8

LVT_K66_TRANDUYBAO đã bình luận lúc 13, Tháng 7, 2025, 10:18

xin dowvote

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-12
haiduong151109 đã bình luận lúc 2, Tháng 6, 2025, 11:18
include<bits/stdc++.h>

using namespace std; int const N=5e4+10; vector<int> adj[N]; int cnt=0; int bridge=0; int khop=0; int low[N],num[N]; void dfsck(int u,int p) { low[u]=num[u]=++cnt; int node=(p!=0); ///if node = 0 tuc la p = 0 va p la goc node = 1 tuc l p k phai la goc viet tat cua if(p==0 for(auto v:adj[u]) { if(v==p) continue; if(!num[v]) { dfsck(v,u); low[u]=min(low[u],low[v]); ///tree edge if(low[v]>num[u]) bridge++; if(low[u]>=num[u]) node++; } else low[u]=min(low[u],num[v]); ///back edge k dùng low v vì chx chắc nó đã cập nhập xong } if(node>1) khop++; } int main() { cin.tie(0)->syncwithstdio(false); int n,m; cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; adj[u].pushback(v); adj[v].pushback(u); } for (int i = 1; i <= n; i++) if (!num[i]) dfs_ck(i, 0);

cout<<khop<<" "<<bridge;

} code em loi dau a :_)
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

5

Free_De_La_Zenith đã bình luận lúc 18, Tháng 3, 2025, 7:37

Nếu bạn bị dính WA 2 test cuối và muốn biết lí do tại sao sai: Input có thể cho một đồ thị không liên thông

-14

phanthedan2009 đã bình luận lúc 14, Tháng 2, 2025, 7:48

This comment is hidden due to too much negative feedback. Show it anyway.

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-6

avatarstar1133 đã bình luận lúc 13, Tháng 2, 2025, 13:54

trùm trường Chuyên Bến Tre

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-54

tandochuyentin2022 đã bình luận lúc 3, Tháng 9, 2024, 8:26

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

17

levanhuyluc đã bình luận lúc 3, Tháng 9, 2024, 7:06

Nếu bạn đã hoàn thành bài này và cảm thấy khá tốt thì hãy đến với bài khó hơn nhé: Đây là bài khó hơn: https://lqdoj.edu.vn/problem/upgrade Ở bài này các bạn phải vận dụng thêm là thuật toán Dijkstra và xây 1 đồ thị con để tối ưu Chúc các bạn thành công nhé ❤

-5

nhanphamj đã bình luận lúc 11, Tháng 7, 2024, 14:56

xin ý tưởng mấy bro

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-6

KienHungg đã bình luận lúc 6, Tháng 6, 2024, 8:37

hello

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

3

BangLee đã bình luận lúc 26, Tháng 5, 2024, 4:09 ← sửa 3 →

Bạn nào mà nộp bằng Python3 hay PyPy3 rất có thể sẽ bị lỗi phần nhập input valueError nếu như nhập bình thường, nếu bạn bị lỗi có thể làm theo cách này:

import sys

input = sys.stdin.read

data = input().split() #(chia nhỏ toàn bộ input và nhập vào data)

n,m = int(data[0]),int(data[1]) #(lúc này trong data[0] và data[1] sẽ tương ứng là n và m)

index = 2 #(đặt biến index để duyệt những phần nhập số liệu còn lại)

for _ in range(m):

u,v = int(data[index]), int(data[index + 1]) #nhập cạnh u,v từ dữ liệu trong data

index += 2 # nhớ là tăng index sau mỗi lần

Chúc các bạn k bị lỗi ValueError

-2

messizutaki đã bình luận lúc 2, Tháng 10, 2024, 6:02 ← chỉnh sửa →

cảm ơn nhiều ạ:))

-91

nthquan_1505 đã bình luận lúc 16, Tháng 3, 2023, 9:19

thembulul

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-48

yanwe111 đã bình luận lúc 22, Tháng 3, 2023, 3:32

bạn bị mắm tôm ám ư

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-87

chubedanye đã bình luận lúc 16, Tháng 3, 2023, 7:10

thembukhu

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-53

nthquan_1505 đã bình luận lúc 15, Tháng 3, 2023, 4:50 ← chỉnh sửa →

.

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-44

ducdacoder3103 đã bình luận lúc 16, Tháng 3, 2023, 7:11

Sao ban lai bi tru 5 vay ban

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-39

yanwe111 đã bình luận lúc 22, Tháng 3, 2023, 3:32

bạn bị mắm tôm ám à

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-45

chubedanye đã bình luận lúc 16, Tháng 3, 2023, 7:09

bạn ơi sao bạn bị -3 vâyh

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-24

hoangheovn đã bình luận lúc 13, Tháng 3, 2023, 8:55

a~x^2~ +bx + c =0 :D

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

18

21ti_hdhphat đã bình luận lúc 13, Tháng 2, 2023, 17:07

Nếu bạn bị dính WA 2 test cuối và muốn biết lí do tại sao sai:

Input có thể cho một đồ thị không liên thông

-41

maintainit đã bình luận lúc 22, Tháng 2, 2023, 12:40

orz

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.