题目真心分析不出来。看了白书才明白，不过有点绕脑。
容易想到，把题目给的不相邻的关系，利用矩阵，反过来建图。既然是全部可行的关系，那么就应该能画出含奇数个点的环。求环即是求双连通分量：找出所有的双连通分量，只要分量中的点数是奇数，则排除“must be expelled”的可能性。
判环上的点数用二分图，这个我都想了半天= =，如果是奇数个点，明摆着多出来的一个点放到哪个集合都会与集合内的点连边（这个找三个点自己画画试试就明白了）。0、1染色，本人喜欢用bfs，递归什么的其实都可以。
我自己用缩点做的，果断wa到吐。举个例子：五个点，{1,2,3}{3,4,5}，这样3就是一个割顶了，缩点的话是在遍历完邻接表之后，再判断low[u]==dfn[u]，如此5个点就缩成了一个点，即一个分量，虽然这个分量包含奇数个点，输出同样是0，但与我们的思路是不一样的。实际情况是分成两个分量，每个分量有三个点，割顶3同时出现在两个分量中。然后想着改进，当把割顶弹出栈后，再弹入，搞啊搞，还是算了，学着白书上用边搞。
#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std; const int MAXN=; struct EDGE{
int u,v;
EDGE(){}
EDGE(int _u,int _v):u(_u),v(_v){}
}; struct Edge{
int v,next;
Edge(){}
Edge(int _v,int _next):v(_v),next(_next){}
}edge[MAXN*MAXN]; int mp[MAXN][MAXN],tol,head[MAXN];
int low[MAXN],dfn[MAXN],bccno[MAXN],iscut[MAXN],TT,bcc_cnt;
int que[MAXN],color[MAXN];
int sign[MAXN]; vector<int >bcc[MAXN];
stack<EDGE >stk; void init()
{
tol=;
memset(head,-,sizeof(head));
} void add(int u,int v)
{
edge[tol]=Edge(v,head[u]);
head[u]=tol++;
} void dfs(int u,int fa)
{
low[u]=dfn[u]=++TT;
int son=;
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].v;
EDGE e=EDGE(u,v);
if(!dfn[v]){
stk.push(e);
son++;
dfs(v,u);
low[u]=min(low[v],low[u]);
if(low[v]>=low[u]){
iscut[u]=;
bcc_cnt++;
bcc[bcc_cnt].clear();
while()
{
EDGE x=stk.top();
stk.pop();
if(bccno[x.u]!=bcc_cnt){
bcc[bcc_cnt].push_back(x.u);
bccno[x.u]=bcc_cnt;
}
if(bccno[x.v]!=bcc_cnt){
bcc[bcc_cnt].push_back(x.v);
bccno[x.v]=bcc_cnt;
}
if(x.u==u&&x.v==v)
break;
}
}
}else if(dfn[v]<dfn[u]&&v!=fa){
stk.push(e);
low[u]=min(low[u],dfn[v]);
}
}
if(fa<&&son==)
iscut[u]=;
} void find_bcc(int n)
{
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
memset(bccno,,sizeof(bccno));
memset(iscut,,sizeof(iscut)); TT=bcc_cnt=; for(int i=;i<=n;i++)
if(!dfn[i])
dfs(i,-);
} bool bfs(int x,int fa)
{
int l,r;
l=r=;
que[r++]=x;
while(l<r)
{
int u=que[l++];
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].v;
if(bccno[v]!=fa)
continue ;
if(color[v]==-){
color[v]=color[u]^;
que[r++]=v;
}else if(color[v]==color[u])
return false;
}
}
return true;
} void Bjudge()
{
memset(sign,,sizeof(sign));
for(int i=;i<=bcc_cnt;i++)
{
memset(color,-,sizeof(color));
for(int j=;j<bcc[i].size();j++)
bccno[bcc[i][j]]=i;
int u=bcc[i][];
color[u]=;
if(!bfs(u,i)){
for(int j=;j<bcc[i].size();j++)
sign[bcc[i][j]]=;
}
}
} int main()
{
int n,m;
int a,b;
while(~scanf("%d%d",&n,&m)!=EOF)
{
if(!n&&!m)
break;
memset(mp,,sizeof(mp));
for(int i=;i<m;i++)
{
scanf("%d%d",&a,&b);
mp[a][b]=mp[b][a]=;
} init();
for(int i=;i<=n;i++)
{
for(int j=i+;j<=n;j++)
{
if(!mp[i][j]){
add(i,j);
add(j,i);
}
}
} find_bcc(n); Bjudge(); int ans=;
for(int i=;i<=n;i++)
if(!sign[i])
ans++;
printf("%d\n",ans);
}
return ;
}
/*
5 4
1 4
1 5
2 4
2 5 6 8
1 4 1 5 1 6
2 4 2 5 2 6
3 4 3 5
*/
最近做了几道connectivity的题目，总结一下。
关于割顶、桥、双连通、边双连通，以及强连通处理方式有其相似性，关键都与时间戳有关。
其中，割顶->双连通 是low[v]>=dfn[u]，桥->边双连通 是low[v]>dfn[u]，只是一个等号的差别，其他处理基本相同；而强连通总是伴随着缩点 low[u]==dfn[u]（这个一般是做边标记edge[].vis，这样即使是无向图也可以以edge[i^1].vis标记掉，而不影响重边的情况）。事实上，如果不考虑具体的桥，对边-双连通分量的划分就是在做无向图上的缩点操作。
这三个判定条件的位置也有不同。缩点是在遍历完u的邻接表之后，用每个low[v]的值更新low[u]，并且u本身不会连到祖先去（这一点很重要），则是一个环，可以缩掉；在无向图中，判断双连通分量，也就是割顶（边-双连通分量&桥 一样），是每遍历一个孩子v，就要判断：low[v]>=dfn[u],只要点u的孩子所能到达的最大值不超过u，那么u就是割顶（删除u后，该子树独立），当然，u的每一个孩子v都可以是被 割顶u 分离，注意u本身是可以与它的祖先连接的！！