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

Points: 0.14 (partial)

Time limit: 1.0s

Memory limit: 512M

Input: stdin

Output: stdout

Problem source:

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

Problem type

Allowed languages

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

Comments

Comments

Please read the guidelines before commenting.

0

hoangquys commented on Dec. 29, 2025, 3:03 p.m.

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

vominhmanh10 commented on Nov. 1, 2025, 8:00 a.m. ← edit 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)

-7

yureki3657 commented on Aug. 31, 2025, 10:22 a.m.

imgay

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

2

tadanhdat123 commented on Aug. 9, 2025, 5:52 a.m. ← edited →

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

2

pppssslc commented on Aug. 9, 2025, 6:57 a.m. ← edited →

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

3

tadanhdat123 commented on Aug. 9, 2025, 8:40 a.m. ← edit 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 commented on July 26, 2025, 1:55 a.m.

xin dowvote

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

-8

LVT_K66_TRANDUYBAO commented on July 13, 2025, 10:18 a.m.

xin dowvote

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

-13
haiduong151109 commented on June 2, 2025, 11:18 a.m.
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 :_)
This comment is hidden due to too much negative feedback. Show it anyway.

5

Free_De_La_Zenith commented on March 18, 2025, 7:37 a.m.

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 commented on Feb. 14, 2025, 7:48 a.m.

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

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

-6

avatarstar1133 commented on Feb. 13, 2025, 1:54 p.m.

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

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

-54

tandochuyentin2022 commented on Sept. 3, 2024, 8:26 a.m.

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

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

17

levanhuyluc commented on Sept. 3, 2024, 7:06 a.m.

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 commented on July 11, 2024, 2:56 p.m.

xin ý tưởng mấy bro

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

-6

KienHungg commented on June 6, 2024, 8:37 a.m.

hello

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

3

BangLee commented on May 26, 2024, 4:09 a.m. ← edit 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 commented on Oct. 2, 2024, 6:02 a.m. ← edited →

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

-91

nthquan_1505 commented on March 16, 2023, 9:19 a.m.

thembulul

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

-48

yanwe111 commented on March 22, 2023, 3:32 a.m.

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

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

-87

chubedanye commented on March 16, 2023, 7:10 a.m.

thembukhu

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

-53

nthquan_1505 commented on March 15, 2023, 4:50 a.m. ← edited →

.

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

-44

ducdacoder3103 commented on March 16, 2023, 7:11 a.m.

Sao ban lai bi tru 5 vay ban

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

-39

yanwe111 commented on March 22, 2023, 3:32 a.m.

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

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

-45

chubedanye commented on March 16, 2023, 7:09 a.m.

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

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

-24

hoangheovn commented on March 13, 2023, 8:55 a.m.

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

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

18

21ti_hdhphat commented on Feb. 13, 2023, 5:07 p.m.

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 commented on Feb. 22, 2023, 12:40 p.m.

orz

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