题目：Knights of the Round Table
第一次做
思路：
tarjan判点双连通分量+二分图染色
注意：
1、要搞清楚无向图的双连通分量和有向图的强连通分量的区别
2、这题初始化的有点多，要注意初始化的位置
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 1000
#define maxm 1000000struct Edge {int x,y;Edge(int xx=0,int yy=0) {x=xx,y=yy;}
};int n,m;bool g[maxn+5][maxn+5];
vector<int> a[maxn+5];int pre[maxn+5],low[maxn+5];
int clk=0;vector<int> bcc[maxn+5];
int cnt=0;stack<Edge> s;bool b[maxn+5]= {0};int col[maxn+5]= {0};
bool In[maxn+5]= {0};void init() { //初始化for(int i=0; i<=maxn; i++) {a[i].clear();bcc[i].clear();}memset(g,0,sizeof(g));memset(pre,0,sizeof(pre));memset(low,0,sizeof(low));memset(b,0,sizeof(b));clk=cnt=0;stack<Edge> emp;s=emp;
}void readin() { //读入，建图for(int i=1; i<=m; i++) {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=1; j<=n; j++) {if(i!=j&&!g[i][j]) a[i].push_back(j);}}
}void tj(int u,int fa) { //tarjanpre[u]=low[u]=++clk;for(int i=0; i<a[u].size(); i++) {int v=a[u][i];if(v==fa) continue;if(!pre[v]) {s.push(Edge(u,v));tj(v,u);low[u]=min(low[v],low[u]);if(low[v]>=pre[u]) {cnt++;Edge x;map<int,bool> h;do {x=s.top();s.pop();if(!h.count(x.x)) h[x.x]=true,bcc[cnt].push_back(x.x);if(!h.count(x.y)) h[x.y]=true,bcc[cnt].push_back(x.y);} while(x.x!=u||x.y!=v);}} else if(pre[v]<pre[u]) {s.push(Edge(u,v));low[u]=min(pre[v],low[u]);}}
}bool Even(int x,int w) { //判二分图col[x]=w;for(int i=0; i<a[x].size(); i++) {int y=a[x][i];if(!In[y]) continue;if(col[y]==col[x]) return false;if(!col[y]) {if(!Even(y,3-col[x])) return false;}}return true;
}void find_odd() {for(int i=1; i<=cnt; i++) {memset(In,0,sizeof(In));memset(col,0,sizeof(col)); //注意col的初始化要写在这里，因为不同双连通分量之间并非不相互影响，它们共着割点 for(int j=0; j<bcc[i].size(); j++) {In[bcc[i][j]]=true;}if(!Even(bcc[i][0],1)&&bcc[i].size()>2) {for(int j=0; j<bcc[i].size(); j++) {b[bcc[i][j]]=true;}}}
}void print() {int ans=0;for(int i=1; i<=n; i++) {if(!b[i]) ans++;}printf("%d\n",ans);
}int main() {while(~scanf("%d%d",&n,&m)&&n) {init();readin();for(int i=1; i<=n; i++) {if(!pre[i]) tj(i,-1);}find_odd();print();}return 0;
}