kmjp's blog

競技プログラミング参加記です

LeetCode Weekly Contest 107 : 928. Minimize Malware Spread II

うーん、入力形式が慣れない。
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だけど、あれより簡単じゃない?