本文共 2254 字，大约阅读时间需要 7 分钟。
题目链接：
题目大意：
给出一些骑士，他们之间有的人相互厌恶，不能挨着坐，如果一个骑士不能在任何一个奇环中出现，那么他要被剔除，问最少踢掉多少骑士
题目分析：
首先我们这些骑士要围成一个环，我们知道一个点双连通分量的任意两条边都在同一个简单环上，所以我们将厌恶关系连边，然后求补图，求出补图中的所有的点双连通分量，判断奇环通过染色法，也就是只要在深搜过程中碰到两个相邻的点颜色相同，那么就是奇环，对于每个点双连通分量，只要点双连通分量中存在奇环，那么就一定能够保证该点双连通分量中的骑士都能顺利开上会。而点双连通分量可以通过割点求出，dfs中割点下的部分一定是一个点双通分量，而且是以该割点相连的点为栈顶元素的
代码如下：
#include#include #include #include #define MAXp 1009#define MAXe 1000009using namespace std;struct{ int v; int next;}e[ MAXe*2 ];int head[MAXp],dfn[MAXp],low[MAXp],ts,c,stk[MAXp],r,s,in[MAXp],cnt,color[MAXp],n;bool mp[MAXp][MAXp],flag[MAXp];void add ( int u , int v ){ e[c].v = v; e[c].next = head[u]; head[u] = c++;}//利用染色法判断一个双连通分量是否为一个奇环bool paint ( int u , int y , int pre ){ int i,v; color[u]= y; for ( i = head[u]; i!=-1; i = e[i].next ) { v =e[i].v; if ( in[v] == 1 && v != pre ) { if ( color[v] == -1 ) { if ( paint( v , color[u]^1 , u )) return true; } else if ( color[u] == color[v] ) return true; } } return false;}//利用tarjan求解各个点双连通分量，只要被验证时奇环的点双连通分量的点就能够参加至少一次会议//点双连通分量中的点都在一个简单环中void dfs ( int u , int pre ){ int i,j,v; dfn[u] = low[u] = ++ts; stk[++s] = u; for ( i = head[u] ; i != -1 ; i = e[i].next ) { v = e[i].v; if ( !dfn[v] ) { dfs ( v ,u ); low[u] = min ( low[u],low[v]); //求割点，利用割点划分出点双连通分量 if ( dfn[u] <= low[v] ) { memset ( in , 0 , sizeof (in)); in[u] = 1; while ( stk[s] != v ) { in[stk[s]]=1; s--; } in[v] = 1; s--; memset (color,-1,sizeof(color) ); if ( paint(u , 1 , -1 ) ) { for (j =1 ; j <= n ; j++ ) if ( in[j] == 1 ) flag[j]=true; } } } else if ( v != pre ) low[u] = min ( low[u] , dfn[v] ); }}int main ( ){ int m,u,v,i,j,ans; while ( scanf ("%d%d" , &n , &m ) ) { if ( !n && !m ) break; memset ( mp ,false , sizeof(mp) ); //构造补图 for ( i = 0 ; i
转载地址：http://qpvjn.baihongyu.com/