[UVA] 1364 - Knights of the Round Table

#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
#include<algorithm>
#define MAX 1005
using namespace std;
struct P{
    int u,v;
}edge;
stack<P> sta;
int ma[MAX][MAX],pre[MAX],bccno[MAX],color[MAX],is[MAX],dfs_clock,bcc_cnt=0;
vector<int> s[MAX],bcc[MAX];
int dfs(int u,int fa){
    int lowu,lowv,i;
    lowu=pre[u]=++dfs_clock;
    for(i=0;i<s[u].size();i++){
        int v=s[u][i];
        if(!pre[v]){
            sta.push((P){u,v});
            lowv=dfs(v,u);
            lowu=min(lowu,lowv);
            if(lowv>=pre[u]){
                bcc_cnt++,bcc[bcc_cnt].clear();
                while(1){
                    edge=sta.top(),sta.pop();
                    if(bccno[edge.u]!=bcc_cnt) bcc[bcc_cnt].push_back(edge.u),bccno[edge.u]=bcc_cnt;
                    if(bccno[edge.v]!=bcc_cnt) bcc[bcc_cnt].push_back(edge.v),bccno[edge.v]=bcc_cnt;
                    if(edge.u==u && edge.v==v) break;
                }
            }
        }
        else if(pre[v]<pre[u] && v!=fa){
            sta.push((P){u,v});
            lowu=min(lowu,pre[v]);
        }
    }
    return lowu;
}
int bicolor(int u,int p){
    int i;
    for(i=0;i<s[u].size();i++){
        int v=s[u][i];
        if(bccno[v]!=p) continue;
        if(color[v]==color[u]) return 0;
        if(!color[v]){
            color[v]=3-color[u];
            if(!bicolor(v,p)) return 0;
        }
    }
    return 1;
}
int main(){
    int n,m,i,j,x,y,ans;
    while(scanf("%d%d",&n,&m)!=EOF && n+m){
        memset(ma,0,sizeof(ma));
        memset(pre,0,sizeof(pre));
        memset(is,0,sizeof(is));
        for(i=0;i<n;i++)
            s[i].clear();
        for(i=0;i<m;i++){
            scanf("%d%d",&x,&y);
            x--,y--;
            ma[x][y]=ma[y][x]=1;
        }
        for(i=0;i<n;i++)
            for(j=i+1;j<n;j++)
                if(ma[i][j]==0)
                    s[i].push_back(j),s[j].push_back(i);
        for(i=0;i<n;i++){
            dfs_clock=0;
            memset(bccno,0,sizeof(bccno));
            if(!pre[i]){
                dfs(i,-1);
            }
        }
        for(i=1;i<=bcc_cnt;i++){
            if(bcc[i].size()<=2) continue;
            memset(color,0,sizeof(color));
            for(j=0;j<bcc[i].size();j++)
                bccno[bcc[i][j]]=i;
            color[bcc[i][0]]=1;
            if(!bicolor(bcc[i][0],i)){
                for(j=0;j<bcc[i].size();j++)
                    is[bcc[i][j]]=1;
            }
        }
        ans=n;
        for(i=0;i<n;i++)
            if(is[i])
                ans--;
        printf("%d\n",ans);
    }
}