题面

Sol

弦图最大独立集

做法见上篇博客
# include <bits/stdc++.h>

# define RG register

# define IL inline

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

const int _(205);

typedef long long ll;

IL int Input(){

	RG int x = 0, z = 1; RG char c = getchar();

	for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;

	for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

	return x * z;

}

int n, m, first[_], cnt, label[_], vis[_], ans, best, Q[_];

struct Edge{

	int to, next;

} edge[_ * _];

vector <int> P[_];

IL void Add(RG int u, RG int v){

	edge[cnt] = (Edge){v, first[u]}, first[u] = cnt++;

}

int main(RG int argc, RG char* argv[]){

	Fill(first, -1), Q[0] = n = Input(), m = Input();

	for(RG int i = 1; i <= m; ++i){

		RG int u = Input(), v = Input();

		Add(u, v), Add(v, u);

	}

	for(RG int i = 1; i <= n; ++i) P[0].push_back(i);

	for(RG int i = 1, nw; i <= n; ++i){

		for(RG int flg = 0; !flg; ){

			for(RG int j = P[best].size() - 1; ~j; --j){

				if(vis[P[best][j]]) P[best].pop_back();

				else{

					nw = P[best][j], flg = 1;

					break;

				}

			}

			if(!flg) --best;

		}

		vis[nw] = 1, Q[Q[0]--] = nw;

		for(RG int e = first[nw]; e != -1; e = edge[e].next)

			if(!vis[edge[e].to]){

				P[++label[edge[e].to]].push_back(edge[e].to);

				best = max(best, label[edge[e].to]);

			}

	}

	Fill(vis, 0);

	for(RG int i = 1; i <= n; ++i){

		if(vis[Q[i]]) continue;

		++ans, vis[Q[i]] = 1;

		for(RG int e = first[Q[i]]; e != -1; e = edge[e].next)

			vis[edge[e].to] = 1;

	}

	printf("%d\n", ans);

    return 0;

}
巴特西

[TJOI2007]小朋友

题面

Sol

最新文章

热门文章
