REFORM – SPOJ

Đề bài:

Thuật toán:

    Đề 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:

    • 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.

    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;
}
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.
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Comments

  1. Code rất dễ hiểu! Thank you!

  2. Code rất dễ hiểu! Thank you!
    Thân!

Speak Your Mind

*