Đề bài:
Thuật toán:
- Loại bỏ một cạnh trong m cạnh của đồ thị
- Thêm một cạnh mới vào đồ thị (cạnh này phải khác m cạnh lúc đầu) sao cho
đồ thị mới đảm bảo tính liên thông.
Đề trên SPOJ bị thiếu, bài này có giới hạn n<=10^5, m<=2*10^5.
Ta có thể phát biểu bài toán dưới dạng đồ thị như sau:
Cho Một đồ thị vô hướng với n đỉnh và m cạnh, mục tiêu của ta là đếm số
cách khác nhau để thực hiện 2 bước sau:
Ta có nhận xét là do chỉ có thể thêm một cạnh vào đồ thị, do đó số lượng
thành phần liên thông của đồ thị chỉ có thể tối đa là 2. Ta sẽ chia bài
toán làm 2 trường hợp: Đồ thị gồm 1 thành phần liên thông và đồ thị gồm
2 thành phần liên thông.
Trường hợp thứ nhất – trường hợp đơn giản hơn: Đồ thị gồm 2 thành phần liên thông
Giả sử 2 thành phần liên thông của đồ thị có số đỉnh lần lượt là C1 và C2
(tất nhiên C1 = n – C2). Do đồ thị có 2 thành phần liên thông, cạnh ta
thêm vào phải là cạnh từ thành phần liên thông này sang thành phần liên
thông kia, có nghĩa là có C1 * C2 cách thêm cạnh, và các cạnh này chắc
chắn khác với m cạnh lúc đầu. Tuy nhiên ta có thêm nhận xét là cạnh bị
loại đi không được phép là cầu. Từ đó, giả sử số cầu của đồ thị là c,
kết quả của ta là (m-c) * C1 * C2.
Trường hợp thứ hai: Đồ thị có duy nhất một thành phần liên thông
Cố định cạnh bỏ đi (xét từng cạnh trong m cạnh của đồ t), ta sẽ chia bài
toán làm 2 trường hợp:
Trường hợp đầu tiên: cạnh bỏ đi không phải là cầu, khi đó đồ thị vẫn tiếp
tục liên thông. Tức là ta có thể thêm bất cứ cạnh nào miễn sau cạnh đó khác
m cạnh lúc đầu là được, như vậy lúc này ta có n(n-1) / 2 – m cách thêm
cạnh mới.
Trường hợp thứ hai: cạnh bỏ đi là cầu, khi đó đồ thị sẽ bị chia làm 2 thành
phần liên thông, và cạnh thêm vào chắc chắn phải nối một đỉnh từ thành phần
liên thông này sang đỉnh thuộc thành phần liên thông kia (để đảm bảo tính
chất liên thông của đồ thị). Gọi C1 và C2 là số lượng đỉnh trong 2 thành
phần liên thông sau khi bỏ đi cạnh đang xét, ta sẽ có C1 * C2 – 1 cách thêm
cạnh mới vào (-1 do trong C1 * C2 cạnh thì có một cạnh trùng với cạnh vừa bỏ
đi).
Lấy tổng số cách trong các trường hợp, ta thu được kết quả của bài toán.
Độ phức tạp: O(m + n)
Code:
#include <bits/stdc++.h> #define FORE(i, a, b) for(int i = a; i <= b; i++) #define FORD(i, a, b) for(int i = a; i >= b; i--) #define FOR(i, a, b) for(int i = a; i < b; i++) const int MAXN = 1e5 * 5; const int INF = 1e9 + 7; using namespace std; int n, m; bool a[50][50]; typedef pair<int, int> ii; vector< ii > s1, s2; int dem; bool Free[50]; inline void duyet(int u) { //cout<<u<<endl; dem++; Free[u] = 0; FORE(v, 1, n) if (u != v && a[u][v] && Free[v] > 0){ duyet(v); } } vector< int > adj[MAXN]; int Low[MAXN], Num[MAXN], Count = 0, Pa[MAXN], C[MAXN]; inline void dfs(int u) { Count++; Num[u] = Count; Low[u] = n + 1; C[u] = 1; FOR(i, 0, adj[u].size()){ int v = adj[u][i]; if (Pa[v] == 0){ Pa[v] = u; dfs(v); C[u] += C[v]; Low[u] = min(Low[u], Low[v]); } else if (Pa[u] != v) Low[u] = min(Low[u], Num[v]); } } long long sd[3]; int main() { ios::sync_with_stdio(0); cin.tie(0); #ifndef ONLINE_JUDGE freopen("REFORM.inp", "r", stdin); freopen("REFORM.out", "w", stdout); #endif //yeulaptrinh.pw cin >> n >> m; if (n <= 20){ FORE(i, 1, m){ int x, y; cin >> x >> y; a[x][y] = 1; a[y][x] = 1; } long long ans = 0; FORE(x, 1, n) FORE(y, x + 1, n) if (a[x][y] == 1){ s2.push_back(ii(x, y)); } else s1.push_back(ii(x, y)); FOR(i, 0, s1.size()) FOR(j, 0, s2.size()){ int u1 = s1[i].first, v1 = s1[i].second; int u2 = s2[j].first, v2 = s2[j].second; a[u1][v1] = 1; a[v1][u1] = 1; a[u2][v2] = 0; a[v2][u2] = 0; memset(Free, 1, sizeof(Free)); dem = 0; // cout<<u1<<" "<<v1<<" "<<u2<<" "<<v2<<endl; duyet(1); if (dem == n) ans++; a[u1][v1] = 0; a[v1][u1] = 0; a[u2][v2] = 1; a[v2][u2] = 1; } cout << ans << endl; } else { int u, v; FORE(i, 1, m){ cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } int dlt = 0; FORE(u, 1, n) if (Pa[u] == 0){ Pa[u] = -1; Count = 0; dfs(u); dlt++; sd[dlt] = Count; } //cout<<dlt<<"??"<<endl; if (dlt > 2){ cout << 0 << endl; return 0; } //FORE(u, 1, n) cout << C[u]<<" ";cout<<endl; long long ans = 0, Cau = 0, SZ = 1LL * n * (n - 1) / 2; FORE(v, 1, n){ u = Pa[v]; if (u == -1 || Low[v] < Num[v]) continue; ans += 1LL * C[v] * (n - C[v]) - 1; Cau++; } //cout << Cau<<"??"<<ans<<endl; if (dlt == 1){ ans += 1LL * (m - Cau) * (SZ - m); cout << ans; } else{ long long ans = 1LL * sd[1] * sd[2] * (m - Cau); cout << ans; } } return 0; } |
- Pascal : https://ideone.com/bhi9Kc
const fi=''; nmax=1000000; mmax=400000; type data=longint; var f:text; adj,x,y:array[0..mmax+1] of data; head:array[0..nmax+1] of data; sl:array[0..nmax+1] of int64; low,num,tr:array[0..nmax+1] of data; n,m,dinh,lab,sl1,res,khop,cau:int64; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); read(f,n,m); for i:=0 to n+1 do head[i]:=0; for i:=1 to m do begin read(f,x[i],y[i]); inc(head[x[i]]); inc(head[y[i]]); end; for i:=1 to n+1 do head[i]:=head[i-1]+head[i]; for i:=1 to m do begin adj[head[x[i]]]:=y[i]; dec(head[x[i]]); adj[head[y[i]]]:=x[i]; dec(head[y[i]]); end; close(f); end; function min(a,b:data):data; begin if a<b then exit(a); exit(b); end; procedure dfs(u:data); var v,k,i:data; s:boolean; begin inc(lab); low[u]:=lab; num[u]:=lab; k:=0; sl[u]:=1; s:=false; for v:=head[u]+1 to head[u+1] do if tr[u]<>adj[v] then begin if num[adj[v]]=0 then begin tr[adj[v]]:=u; inc(k); dfs(adj[v]); if low[adj[v]]>=num[u] then s:=true; sl[u]:=sl[adj[v]]+sl[u]; low[u]:=min(low[u],low[adj[v]]); end else low[u]:=min(low[u],num[adj[v]]); end; if ((s and (tr[u]<>0)) or ((tr[u]=0) and (k>1))) then inc(khop); if (Low[u]=num[u]) and (tr[u]<>0) then inc(cau); end; procedure ddfs(u:data); var v:data; begin inc(dinh); num[u]:=1; for v:=head[u]+1 to head[u+1] do if num[adj[v]]=0 then ddfs(adj[v]); end; procedure xuli; var i,j:data; stplt:int64; begin for i:=1 to n do num[i]:=0; stplt:=0; sl1:=0; for i:=1 to n do if num[i]=0 then begin dinh:=0; ddfs(i); if sl1=0 then sl1:=dinh; inc(stplt); end; if stplt>2 then begin writeln('0'); exit; end; for i:=1 to n do num[i]:=0; tr:=num; cau:=0; khop:=0; lab:=0; for i:=1 to n do if num[i]=0 then dfs(i); if stplt=1 then begin res:=(m-cau)*((n*(n-1)) div 2 - m); for i:=2 to n do if low[i]=num[i] then res:=res+int64(sl[i])*(int64(n-sl[i]))-1; writeln(res); exit; end; if stplt=2 then begin res:=(m-cau)*sl1*(n-sl1); writeln(res); end; end; begin docfile; xuli; end. |
BÌNH LUẬN MỚI