aoj2564:Tree Reconstruction
解法
連結成分が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; }