[UVA1364

评测地址：
网址1
网址2

题目描述：

题意：

给出n位骑士，然后有m个关系，每个关系以格式:
a   b a\ b a b给出，表达骑士 a a a不能和 b b b相邻，问要想使得最多的奇数个骑士在一起围成一圈，要剔除多少人

solution：

一. part1 : 首先解决这道题要用到的知识点：
1. 建立补图
2. Tarjan求解点双连通分量(V-DCC)并记录 洛谷模板题
3. 奇环
4. 二分图的判定(二分图染色)
二. part2 概念解析：

1. 所谓补图，就是将原图中连着的边去掉，而将原来没有连的边连接起来。加入原图为 G G G，我们设其补图为 G ′ G' G′，那么说满足以下两个条件：
   G ∩ G ′ = ∅ G \cap G' = \varnothing G∩G′=∅
   G ∪ G ′ = U G \cup G' = U G∪G′=U
   其中 U U U代表全集，即包含 n n n个点， ( n − 1 ) ∗ n / 2 (n-1)*n/2 (n−1)∗n/2条边的图的集合
2. Tarjan求解点双连通分量的过程和求解边双连通分量的过程稍有不同，可以参考博客，这里直接截图引入：
   
   
3. 奇环
   一个环内，有奇数个点，那么这个环就是个奇环
4. 二分图的判定
   用二分图染(交叉)色的方法可以判断图是不是一个二分图
   三. part3 思路解析
   1. 发现直接用给出的数据不好进行处理，因为给出的是不能相邻的关系，这里我们逆向思考，建立补图，然后图的意义就发生了翻天覆地的变化：
      由原本相连的边是不能相邻的关系转换成了相连的点可以相邻
   2. 根据题中的要求，要使得相邻的两个人靠在一起，说明能够满足条件的骑士的度数必定 ≥ 2 \geq 2 ≥2，所以说对于那些点的度数 ≤ 1 \leq 1 ≤1的点，都是要被剔除的。
      哪些点要被剔除呢？
      
      图片来源
      我们可以很轻松地发现，被提出的都是在点双连通分量之外的，比如该图中的 1 1 1 和 5 5 5，那么怎么判断哪些点不在环中呢？
      此时我们还可以逆向思考， 不 在 环 中 的 = = 总 的 − 在 环 中 不在环中的 == 总的 - 在环中 不在环中的==总的−在环中的，所以说现在问题就转换成了满足条件的环内的点的个数
   3. 对于那些满足条件的点，留在了环中，但是他们一定满足条件吗？
      答案是不一定，因为环中可能不是奇数个点，可能是偶数个
      对于一个偶数的环，都是要被整体剔除的！
   4. 所以说现在问题就转换成了求一个点双强连通分量是不是有奇环：
      给出一个结论：
      结论1：
      双连通分量含有奇圈，则必定不是一个二分图，反之亦然成立，所以说如果对一个点双强连通分量染色不成功，那么说这个点双强连通分量中必然含有一个奇环
      结论2：
      如果一个V-DCC中有一个奇环,那么该V-DCC所有点都在某一个奇环上.为什么呢?假设有一个奇环上的两个点 x , y x,y x,y,该奇环外一个点zz,因为在同一个V-DCC上, x , y , z x,y,z x,y,z肯定在同一个环上.路径 x → z → y → x x\to z \to y \to x x→z→y→x中,因为 x , y x,y x,y在同一个奇环上, y → x y\to x y→x至少有两条路可以走,并且这两条路的奇偶性不同,因此不管怎样都可以找到一个包含 z z z的奇环 x → z → y → x x\to z\to y \to x x→z→y→x.
      (如果一个点双连通分量内的某些顶点在一个奇环中（即点双连通分量含有奇环），那么这个点双连通分量的其他顶点也在某个奇环中；)
      所以说现在问题就转换成了如何求一个图是不是二分图，这里就用到了二分图交叉染色来处理！
   5. 统计答案
      对于上面统计出来的可以加入的点，我们统一标记起来，比如 j u d g e [ i ] judge[i] judge[i]为1的时候表示这个点可以加入，而为0的时候，表示这个点不可以加入，所以说我们记录答案为 a n s = n ans=n ans=n，遍历n个点，遇到 j u d g e [ i ] = = 1 judge[i] == 1 judge[i]==1的情况时， a n s − − ans-- ans−−即可

至此讲解结束

ac_code:

int n,m,root,cntVDCC;
struct node{
	int u,v,nex;
}e[maxn << 1];
int dfn[maxn],low[maxn],cnt,head[maxn],dfc;
void add(int u,int v) {
	e[cnt].u = u;
	e[cnt].v = v;
	e[cnt].nex = head[u];
	head[u] = cnt ++;
}
typedef pair<int,int> PII;
map<PII,bool> mp;
bool exist[1007][1007];
stack<int> stk;
void ClearStack() {
	while(stk.size()) stk.pop();
}
int col[1007];
vector<int> VDCC[1007];
void _Init() {
	dfc = cntVDCC = cnt = 0;
	root = 0;
	mp.clear();
	for(int i=1;i<=n;i++) {
		head[i] = -1;
		dfn[i] = low[i] = 0;
		col[i] = 0;
		VDCC[i].clear();
	}
}
bool judge[1007],canVis[1007];
void Tarjan(int u){
	dfn[u] = low[u] = ++ dfc;
	if(head[u] == -1 && u == root) {
		++ cntVDCC;
		VDCC[cntVDCC].push_back(u);
	}
	for(int i=head[u];~i;i=e[i].nex) {
		int to = e[i].v;
		if(!dfn[to]) {
			stk.push(to);
			Tarjan(to);
			low[u] = min(low[u],low[to]);
			if(low[to] >= dfn[u]) {
				cntVDCC ++;
				
				while(stk.top() != to) {
					VDCC[cntVDCC].push_back(stk.top());
					stk.pop();
				}
				VDCC[cntVDCC].push_back(stk.top());
				stk.pop();
				VDCC[cntVDCC].push_back(u);
				
				/**
				VDCC[cntVDCC].push_back(u);
				int tp;
				do{
					tp = stk.top();
					stk.pop();
					VDCC[cntVDCC].push_back(tp);
				}while(tp != to);
				**/
			}
		}///else if(to != fa) low[u] = min(low[u], dfn[to]);
		else low[u] = min(low[u], dfn[to]);
	}
}
bool dfs(int u){
	for(int i=head[u];~i;i=e[i].nex) {
		int to = e[i].v;
		if(canVis[to]) {
			if(!col[to]) {
				col[to] = 3 - col[u];
				if(!dfs(to)) return false;
			}else if(col[u] + col[to] != 3) return false;
		}
	}
	return true;
}
int main() {
	while(cin >> n >> m && (n + m)) {
		_Init();
		ClearStack();
		memset(exist,0,sizeof exist);
		for(int i=1;i<=m;i++) {
			int u = read,v = read;
//			mp[{u,v}] = mp[{v,u}] = 1;///TLE罪魁祸首
			exist[u][v] = exist[v][u] = 1;///标记边
		}
		for(int i=1;i<=n;i++){
			for(int j=1+i;j<=n;j++){
//				if(mp[{i,j}]) continue;
				if(exist[i][j]) continue;
				add(i,j);//建立补图
				add(j,i);
			}
		}
		for(int i=1;i<=n;i++){
			if(!dfn[i]) {
				root = i;
				Tarjan(i);
			}
		}
		memset(judge,0,sizeof judge);
		memset(canVis,0,sizeof canVis);
//		debug(cntVDCC);
		for(int i=1;i<=cntVDCC;i++) {
			for(int x:VDCC[i]) canVis[x]=1;///标记为可以通过
			if(!dfs(VDCC[i][0])) {///染色不成功，含有奇环
				for(int x:VDCC[i]) judge[x] = 1;
			}
			for(int x:VDCC[i]) canVis[x]=0,col[x]=0;///撤销标记以及颜色
		}
		int ans = n;//统计答案
		for(int i=1;i<=n;i++) {
			if(judge[i]) -- ans;
		}
		printf("%d\n",ans);
	}
	return 0;
}