评测地址：
题目描述：
题意：
给出n位骑士，然后有m个关系，每个关系以格式:
a b给出，表达骑士a 不能和b 相邻，问要想使得最多的奇数个骑士在一起围成一圈，要剔除多少人
solution：
一. part1 : 首先解决这道题要用到的知识点：
1. 建立补图
2. Tarjan求解点双连通分量(V-DCC)并记录 洛谷模板题
3. 奇环
4. 二分图的判定(二分图染色)
二. part2 概念解析：
- 所谓补图，就是将原图中连着的边去掉，而将原来没有连的边连接起来。加入原图为G，我们设其补图为G ′ ，那么说满足以下两个条件：
G ∩ G ′ = ∅
G ∪ G ′ = U
其中U 代表全集，即包含n 个点，( n − 1 ) ∗ n / 2 条边的图的集合
- Tarjan求解点双连通分量的过程和求解边双连通分量的过程稍有不同，可以参考博客，这里直接截图引入：
奇环
一个环内，有奇数个点，那么这个环就是个奇环
二分图的判定
用二分图染(交叉)色的方法可以判断图是不是一个二分图
三. part3 思路解析
- 发现直接用给出的数据不好进行处理，因为给出的是不能相邻的关系，这里我们逆向思考，建立补图，然后图的意义就发生了翻天覆地的变化：
由原本相连的边是不能相邻的关系转换成了相连的点可以相邻
- 根据题中的要求，要使得相邻的两个人靠在一起，说明能够满足条件的骑士的度数必定≥ 2 \geq 2≥2，所以说对于那些点的度数≤ 1 \leq 1≤1的点，都是要被剔除的。
哪些点要被剔除呢？
我们可以很轻松地发现，被提出的都是在点双连通分量之外的，比如该图中的1 和 5 ，那么怎么判断哪些点不在环中呢？
此时我们还可以逆向思考，不 在 环 中 的 = = 总 的 − 在 环 中 的，所以说现在问题就转换成了满足条件的环内的点的个数
对于那些满足条件的点，留在了环中，但是他们一定满足条件吗？
答案是不一定，因为环中可能不是奇数个点，可能是偶数个
对于一个偶数的环，都是要被整体剔除的！
所以说现在问题就转换成了求一个点双强连通分量是不是有奇环：
给出一个结论：
结论1：
双连通分量含有奇圈，则必定不是一个二分图，反之亦然成立所以说如果对一个点双强连通分量染色不成功，那么说这个点双强连通分量中必然含有一个奇环
结论2：
如果一个V-DCC中有一个奇环,那么该V-DCC所有点都在某一个奇环上.为什么呢?假设有一个奇环上的两个点x , y ,该奇环外一个点zz,因为在同一个V-DCC上,x , y , z 肯定在同一个环上.路径x → z → y → x 中,因为x , y 在同一个奇环上,y → x 至少有两条路可以走,并且这两条路的奇偶性不同,因此不管怎样都可以找到一个包含z 的奇环x → z → y → x
(如果一个点双连通分量内的某些顶点在一个奇环中（即点双连通分量含有奇环），那么这个点双连通分量的其他顶点也在某个奇环中；)
所以说现在问题就转换成了如何求一个图是不是二分图，这里就用到了二分图交叉染色来处理！
统计答案
对于上面统计出来的可以加入的点，我们统一标记起来，比如 judge[i] 为1的时候表示这个点可以加入，而为0的时候，表示这个点不可以加入，所以说我们记录答案为 ans=n，遍历n个点，遇到 judge[i] == 1 的情况时，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; }
![[Nowcoder] network | Tarjan 边双连通分量 | 缩点 | LCA倍增优化 | 并查集](https://ucc.alicdn.com/pic/developer-ecology/5554eff79239411c8300cad4838b1fe7.png?x-oss-process=image/resize,h_160,m_lfit)
