yukicoder No.330 Eigenvalue Decomposition
解法
行列 A の (ak, bk) 成分及び (bk, ak) 成分が 0 のとき, 頂点 ak と bk の間に辺を結ぶ, ということをすると, この問題の答えは, グラフ上の連結成分の個数になります。
証明については以下が参考になりそうです。
lab.adn-mobasia.net
struct UnionFind { vector<int> par; int n, cnt; UnionFind(const int& x = 0) {init(x);} void init(const int& x) {par.assign(cnt=n=x, -1);} inline int find(const int& x) {return par[x] < 0 ? x : par[x] = find(par[x]);} inline bool same(const int& x, const int& y) {return find(x) == find(y);} inline bool unite(int x, int y) { if ((x = find(x)) == (y = find(y))) return false; --cnt; if (par[x] > par[y]) swap(x, y); par[x] += par[y]; par[y] = x; return true; } inline int count() const {return cnt;} inline int count(int x) {return -par[find(x)];} }; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M; cin >> N >> M; UnionFind uf(N); for (int i = 0; i < M; i++) { int a, b, c; cin >> a >> b >> c; a--; b--; uf.unite(a, b); } cout << uf.count() << endl; return 0; }
問題見た直後, 数値解析の教科書を引っ張り出してきたけど, 固有値が 0 になる個数ってランクでわかるじゃん, と思ってなんとなく連結成分で出したら通りました。