题目大意
询问有多少个点不在奇环上。
试题分析
性质1
若两人若不在一个点双连通分量中，则无法一起出席。
证明
若两人一起出席，则肯定两点之间构成点双连通分量，但是两者不在一个点双中，不满足点双的极大性，则性质1正确。
性质2
若在点双中有奇环，则每个点都至少在一个奇环上。
证明
我们考虑在奇环上两点$x_i$与$x_j$与$s$,并且又因为奇环的概念所以从$x_i$到$x_j$的路径有奇偶两条，所以无论怎样都可以建立起奇环。
结论
所以说当在一个点双连通分两种存在奇环时，则点双中任意一点都可以出席至少一次会议。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } const int N=1004; const int M=1000001; struct node{ int u,v,nex,vis; }x[M<<1]; int n,m,head[N],cnt,tot,sta[M],dfn[N],low[N],num; void add(int u,int v){ x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],x[cnt].vis=1,head[u]=cnt++; }int rt,mark[N],color[N]; bool find(int f){ for(int i=head[f];i!=-1;i=x[i].nex){ if(!mark[x[i].v]) continue; if(color[x[i].v]==-1){ color[x[i].v]=(1^color[f]); return find(x[i].v); }else if(color[x[i].v]==color[f]) return 1; } return 0; } int del[N],g[N][N]; void query(int f){ memset(color,-1,sizeof(color)); memset(mark,0,sizeof(mark)); do{ mark[x[sta[tot]].u]=1; mark[x[sta[tot]].v]=1; tot--; }while(x[sta[tot+1]].u!=f); color[f]=0; if(find(f)){ for(int i=1;i<=n;i++) if(mark[i]) del[i]=1; } return; } void tarjan(int f){ dfn[f]=low[f]=++num; for(int i=head[f];i!=-1;i=x[i].nex){ if(x[i].vis==-1) continue; x[i].vis=x[i^1].vis=-1; sta[++tot]=i; if(!dfn[x[i].v]){ tarjan(x[i].v); low[f]=min(low[f],low[x[i].v]); if(dfn[f]<=low[x[i].v]) query(f); }else low[f]=min(low[f],dfn[x[i].v]); } } int main(){ // freopen("make.in","r",stdin); while(1){ memset(g,0,sizeof(g)),memset(del,0,sizeof(del)),cnt=0,memset(head,-1,sizeof(head)),num=0,tot=0; memset(low,0,sizeof(low)),memset(dfn,0,sizeof(dfn)); n=read(),m=read(); if(!n&&!m) return 0; for(int i=1;i<=m;i++){ int u=read(),v=read(); g[u][v]=g[v][u]=1; } for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){ if(!g[i][j]) add(i,j),add(j,i); } for(int i=1;i<=n;i++) if(!dfn[i]) rt=i,tarjan(i); int ans=0; for(int i=1;i<=n;i++){ if(!del[i]) ans++; } cout<<ans<<endl; } }