yukicoder : No.330 Eigenvalue Decomposition

知らなかったけど勘で適当なコードを書いたら通ってしまった。
http://yukicoder.me/problems/778

問題

N次正方行列Aがある。
この行列は対称であり、2M個の非対角成分は正であり、パラメータ(a[i],b[i],c[i])に対しA[a[i]][b[i]]=A[b[i]][a[i]]=c[i]の関係を持つ。
それ以外の非対角成分は0である。
対角成分は、行及び列の総和が0になるような値である。

この行列の固有値のうち0の個数を求めよ。

解法

本番、何となくUnion-Findでa[i]とb[i]を連結していき、連結成分の数を数えたらあってた。

このグラフは、多重辺を許可したラプラシアン行列と見なすことができる。
どうもラプラシアンのゼロ固有値の個数とグラフの連結成分の数が等しいそうなので、結果的にUnion-Findで連結成分を求めるのは正しいようです。

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

int N,M;
int is[202020];
int A[202020],B[202020],C[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	UF<202020> uf;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>A[i]>>B[i]>>C[i];
		uf(A[i]-1,B[i]-1);
	}
	
	int cnt=0;
	FOR(i,N) if(uf[i]==i) cnt++;
	
	cout<<cnt<<endl;
	
}

まとめ

こんなの知らなかったんだけど、サクサク解いてる人多いから割と有名な話なのかな。
よく勘で当たったもんだ。