TopCoder SRM 753 Div1 Easy Div2 Hard MaxCutFree

戸惑ったけど一応２問解けて良かった。
https://community.topcoder.com/stat?c=problem_statement&pm=15257

問題

N頂点M辺の無向グラフGが与えられる。
SがGの部分誘導グラフであるとは、G中の辺の両端の頂点がSに含まれるとき、S中でもその間に辺をもつものとする。

Gの部分誘導グラフのうち、G中で橋を成す辺を含まないものの最大頂点数を答えよ。

解法

Mはさほど大きくないので、DFSなりUnion-FindなりでO(M^2)やP(M^2*α(M))かけて橋を列挙しよう。
Gの辺のうち橋だけ残したものを考える。
橋の両端はいずれか片方しか残せない、という条件のもと、Gからできるだけ多くの点を残すことを考える。

幸い、条件から橋だけからなるグラフは森になるので、個々の木に対しDPで残す頂点数を最大化しよう。

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

vector<int> E[1010];
int vis[1010];
int dp[1010][2];
class MaxCutFree {
	public:
	void dfs(int cur,int pre) {
		vis[cur]=1;
		dp[cur][0]=0;
		dp[cur][1]=1;
		FORR(e,E[cur]) if(e!=pre) {
			dfs(e,cur);
			dp[cur][0]+=max(dp[e][0],dp[e][1]);
			dp[cur][1]+=dp[e][0];
		}
	}
	
	int solve(int n, vector <int> a, vector <int> b) {
		int M=a.size();
		int i,j;
		FOR(i,n) E[i].clear();
		FOR(i,M) {
			UF<1050> uf;
			FOR(j,M) if(i!=j) uf(a[j],b[j]);
			if(uf[a[i]]!=uf[b[i]]) {
				E[a[i]].push_back(b[i]);
				E[b[i]].push_back(a[i]);
			}
		}
		
		ZERO(vis);
		ZERO(dp);
		int ret=0;
		FOR(i,n) if(vis[i]==0) {
			dfs(i,-1);
			ret+=max(dp[i][0],dp[i][1]);
		}
		return ret;
		
	}
}

まとめ

300ptなのでちょっとびっくりしたけど無事解けて良かった。