うーん、入力形式が慣れない。
https://leetcode.com/contest/weekly-contest-107/problems/minimize-malware-spread-ii/
問題
N頂点の無向グラフが与えられる。
頂点の一部が感染していたとする。
感染している頂点と辺を共有する頂点は合わせて感染し、それが連鎖的に生じる。
元々感染している頂点のうち、1つ頂点およびそこにつながる辺を削除できるとする。
感染頂点数の最小値を求めよ。
解法
感染している頂点群からDFSなりBFSすれば、最終的に感染する頂点数はO(N^2)で求まる。
よって取り除く頂点を総当たりしてもO(N^3)で間に合う。
int C[303]; class Solution { public: int minMalwareSpread(vector<vector<int>>& G, vector<int>& initial) { int N=G.size(); int x,y,z,i; int mi=101010; int be=01; sort(ALL(initial)); FORR(x,initial) { int c=0; ZERO(C); queue<int> Q; FORR(y,initial) if(x!=y) { Q.push(y); C[y]=1; } while(Q.size()) { y=Q.front(); Q.pop(); c++; FOR(i,N) if(i!=x && G[y][i] && C[i]==0) { C[i]=1; Q.push(i); } } if(c<mi) mi=c,be=x; } return be; } };
まとめ
108回目のDは難易度6だけど、あれより簡単じゃない?