aoj2564:Tree Reconstruction

問題文

Tree Reconstruction | Aizu Online Judge

解法

連結成分が1つしかない場合について考える

頂点数をn、辺の数をmとする。

各辺の値をxiとおいて、各頂点についての流量保存則を方程式で表してみると、行列を用いて

Ax=0
(
A:n×mの行列
x:xiを縦に並べたm×1の列ベクトル
0:n×1の列ベクトル
)
となる。

0∈kerAであるから、上記の方程式は解を持つ。

求めたいのはdim(kerA)である。
次元定理 rankA +dim(kerA)=mより、
dim(kerA)=m-rankA

よって、rankAを求めればいい。

そのために、Aがどういう構造か考える。

Aの構成:
まず、A=Oとする。
辺i (u→v)に対して、A(u,i)=1 , A(v,i)=-1　とする。

Aを転置してもrankは変わらないから、転置したものをBとする(m×nの行列)

rankBは、Bの各列を列ベクトルと見たとき、そこから選び出せる一次独立なベクトルの本数の最大値である。

B=[v1,v2,...,vn]とする(viはm×1の列ベクトル)

v1+v2+...+vn=0より、これらは一次独立ではないから、rankB!=n
一方、グラフの連結性などより、v1,...,vnからk本(k < n)選びだしたとき、これらは必ず一次独立である。したがって、rankB=n-1がわかる。

以上より、dim(kerA)=m-rankA=m-rankB=m-n+1

連結成分が複数ある場合は、各連結成分について上記の計算を行い、足し合わせればいい。したがって、グラフ全体の頂点数、辺数、連結成分数をそれぞれN,M,Cとすれば、答えはM-N+Cである。

コード

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

struct UnionFindTree{
    vector<int>par,sz;
    UnionFindTree(int n){
        par.resize(n);
        sz.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        sz[x]+=sz[y];
        par[y]=x;
    }
    bool areSame(int x,int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};

int N,M;

signed main(){
    cin>>N>>M;
    UnionFindTree uf(N);
    rep(i,M){
        int a,b;
        cin>>a>>b;
        a--;b--;
        uf.unite(a,b);
    }

    int cnt=0;
    rep(i,N)if(uf.find(i)==i)cnt++;
    cout<<M-N+cnt<<endl;
    return 0;
}