HỆ THỐNG XE BUS

Tác giả:

Dạng bài

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Hệ thống xe bus của thành phố nơi cậu sinh viên \(Z\) đang ở là một đồ thị vô hướng gồm có \(N\) trạm và \(M\) tuyển đường.

Thành phố của cậu đang có kế hoạch bỏ đi một trạm và tuyến đường đã cũ và xây mới trong tương lại. Là một người thường xuyên sử dụng các phương tiện công cộng như xe bus để bảo vệ môi trường, \(Z\) nhận thấy một số trạm và tuyến đường khi nó bị gỡ bỏ sẽ lập tức ảnh hưởng tới việc đi lại.

Hãy giúp \(Z\) đếm số trạm và số tuyến đường nếu bị gỡ bỏ sẽ có thể làm một vài cặp trạm không thể đi lại được như trước, một cặp trạm được gọi là không thể đi lại được như trước nếu như trước khi gỡ bỏ từ \(u\) có thể đi được với \(v\) nhưng sau khi bỏ đi một trạm hoặc tuyển đường nào đó thì \(u\) không thể đi được tới \(v\) nữa.

Input

Dòng đầu tiên gồm hai số \(N\) và \(M\) (\(1 \le n \le 10000, 1 \le m \le 50000\)) lần lượt là số trạm và số tuyến đường.
\(M\) dòng tiếp theo, mỗi dòng gồm \(2\) số \(u\) và \(v\) (\(1 \le u, v \le n\)) là hai trạm xe bus có đường đi trực tiếp tới nhau

Output

Gồm hai số lần lượt là số trạm và số tuyến đường nếu bỏ sẽ ngay lập tức gây ảnh hưởng tới việc đi lại.

Example

Test 1

Input

Output

4 3

Note

Các trạm có thể gây ảnh hưởng khi bị bỏ là: \(2\) \(3\) \(7\) \(10\)
Các tuyến đường có thể gây ảnh hưởng khi bị bỏ là: \(2\) \(10,\) \(3\) \(10,\) \(1\) \(10\)

Bình luận

-1
bonniviro123 10:56 a.m. 16 Tháng 9, 2024
bruh,

include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef unsigned long long ull;

define X first

define Y second

define pb push_back

define mp make_pair

define ep emplace_back

define EL printf("\n")

define sz(A) (int) A.size()

define FOR(i,l,r) for (int i=l;i<=r;i++)

define FOD(i,r,l) for (int i=r;i>=l;i--)

define fillchar(a,x) memset(a, x, sizeof (a))

define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

const int N = 10005, inf = N;
int n, m, low[N], num[N], pa[N];
vector<int> a[N];

void dfs(int u) {
num[u] = ++num[0];
low[u] = inf;
for (auto v : a[u]) {
if (v == pa[u]) continue ;
if (num[v]) low[u] = min(low[u], num[v]);
else {
pa[v] = u;
dfs(v);
low[u] = min(low[u], low[v]);
}
}
}

int find_khop() {
int khop[N] = {0}, con[N] = {0};
FOR(v,1,n) {
int u = pa[v];
if (u > 0) con[u]++;
}
FOR(v,1,n) {
int u = pa[v];
if (u > 0 && pa[u] > 0 && low[v] >= num[u]) khop[u] = 1;
}
FOR(u,1,n)
if (pa[u] == 0 && con[u] >= 2) khop[u] = 1;
FOR(u,1,n) khop[0] += khop[u] == 1;
return khop[0];
}

int find_cau() {
int cau = 0;
FOR(v,1,n)
cau += pa[v] > 0 && low[v] >= num[v];
return cau;
}

int main() {
// freopen("INP.TXT", "r", stdin);
// freopen("OUT.TXT", "w", stdout);

scanf("%d%d", &n,&m); FOR(i,1,m) { int u, v; scanf("%d%d", &u,&v); a[u].ep(v); a[v].ep(u); } FOR(u,1,n) if (!num[u]) dfs(u); printf("%d %d\n", find_khop(), find_cau()); return 0;

}

2

minhtuanitk20 11:32 p.m. 25 Tháng 1, 2022

bài này thực chất chỉ là bài đếm khớp cầu