Knights of the Round Table POJ

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio> 
#include<vector>
using namespace std;
const int N = 1e3 + 10;
const int M = 2e6 + 10;
int n, m;
int g[N][N];
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], num, stac[N], top;
int dcc_cnt;
vector<int>dcc[N];
bool cut[N];
int c[N];
int b[N];
int color[N];
bool ok;
void add(int a, int b)
{
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx ++;
}
void tarjan(int u, int root)
{
	dfn[u] = low[u] = ++num;
	stac[++ top] = u;
	if(u == root && h[u] == -1)
	{
		dcc[++dcc_cnt].push_back(u);
		return ;
	}
	int cnt = 0;
	for (int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if(!dfn[j])
		{
			tarjan(j, root);
			low[u] = min(low[u], low[j]);
			if(low[j] >= dfn[u])
			{
				cnt ++;
				if(u != root || cnt > 1)
					cut[u] = true;
				dcc_cnt ++;
				int z;
				do
				{
					z = stac[top --];
					dcc[dcc_cnt].push_back(z);
				}
				while(z != j);
				dcc[dcc_cnt].push_back(u);
			}
		}
		else low[u] = min(low[u], dfn[j]);
	}
}
void dfs(int x, int co, int now)
{
	color[x] = co;
	if(ok)
		return ;
	for (int i = h[x]; ~i; i = ne[i])
	{
		int j = e[i];
		if(c[j] != now)
			continue;
		if(!color[j])
		{
			dfs(j, 3 - co, now);
		}
		//说明存在奇数环
		else if(color[j] == color[x])
		{
			ok = true;
			return ;
		}
	}
}
void init()
{
	num = 0;
	idx = 0;
	dcc_cnt = 0;
	for (int i = 1; i <= n; i ++)
	{
		low[i] = dfn[i] = 0;
		h[i] = -1;
		dcc[i].clear();
		cut[i] = 0;
		b[i] = 0;
		c[i] = 0;
		color[i] = 0;
		for (int j = i + 1; j <= n; j ++)
		{
			g[i][j] = g[j][i] = 0;
		}
	}
}
int main()
{

	while(scanf("%d%d", &n, &m) != EOF)
	{
		if(n == 0 && m == 0)
			break;
		init();
		while(m --)
		{
			int x, y;
			scanf("%d%d", &x, &y);
			g[x][y] = g[y][x] = 1;
		}
		for (int i = 1; i <= n; i ++)
			for (int j = i + 1; j <= n; j ++)
				if(!g[i][j])
					add(i, j), add(j, i);
		for (int i = 1; i <= n; i ++)
			if(!dfn[i])
				tarjan(i, i);
		for (int i = 1; i <= dcc_cnt; i ++)
		{
			for (int j = 0; j < dcc[i].size(); j ++)
			{
				int x = dcc[i][j];
				//当前属于的连通块，因为每个点可能属于多个双连通分量
				c[x] = i;
				color[x] = 0;
			}
			ok = false;
			dfs(dcc[i][0], 1, i);
			//如果存在奇数环
			if(ok)
			{
				//那么这个连通块中的所有的点 就都属于某个奇数环
				for (int j = 0; j < dcc[i].size(); j ++)
					b[dcc[i][j]] = 1;
			}
		}
		int ans = 0;
		for (int i = 1; i <= n; i ++)
			if(!b[i])
				ans ++;
		printf("%d
", ans);
	}
}