蓝书的证明很详细了。
这里说下我做这题遇到的迷惑点：
这里要用e-DCC而非v-DCC，详情见https://blog.csdn.net/bjfu170203101/article/details/107090925
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define ls (o<<1) #define rs (o<<1|1) #define pb push_back const double PI= acos(-1.0); const int M = 1e6+7; const int N = 1e3 +7; int head[2*M],cnt=1; struct EDGE{int to,nxt,w;}ee[M*2]; void add(int x,int y,int w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;} int mp[N][N]; int dfn[N],low[N],sz,rt,sk[M],top; bool cut[M]; int col[N],vs[N],choose[N]; vector<int>dcc[N]; int ct; int n,m; void init() { cnt=1;top=ct=0; memset(choose,0,sizeof(choose)); memset(head,0,sizeof(head)); memset(mp,0,sizeof(mp)); memset(dfn,0,sizeof(dfn)); memset(cut,0,sizeof(cut)); memset(col,0,sizeof(col)); memset(vs,0,sizeof(vs)); for(int i=1;i<=n;i++)dcc[i].clear(); } void tarjan(int x)//保证了不存在重边 { dfn[x]=low[x]=++sz; sk[++top]=x; if(x==rt&&head[x]==0){//孤立点 dcc[++ct].pb(x); //--top; return ; } int fg=0; for(int i=head[x];i;i=ee[i].nxt) { int y=ee[i].to; if(!dfn[y]) { tarjan(y); low[x]=min(low[x],low[y]); if(low[y]>=dfn[x]) { fg++; if(x!=rt||fg>=2) cut[x]=true; ct++; int z; do{ z=sk[top--]; dcc[ct].pb(z); }while(z!=y); dcc[ct].pb(x); } } else low[x]=min(low[x],dfn[y]); } } bool flag; int nm; void dfs(int x,int p) { // cout<<" "<<x<<" "<<p<<endl; col[x]=p; for(int i=head[x];i;i=ee[i].nxt) { int y=ee[i].to; if(!vs[y])continue; if(!col[y])dfs(y,p^1); else if(col[y]==col[x])flag=true; } } int main() { ios::sync_with_stdio(false); cin.tie(0); while(cin>>n>>m) { if(n==0)break; init(); for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; mp[x][y]=mp[y][x]=1; } for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(!mp[i][j])add(i,j,1),add(j,i,1); for(int i=1;i<=n;i++) if(!dfn[i])rt=i,tarjan(i); int ans=0; for(int i=1;i<=ct;i++) { memset(vs,0,sizeof(vs)); for(auto x:dcc[i])vs[x]=1,col[x]=0; //cout<<x<<" "; flag=false;nm=0; dfs(dcc[i][0],2); if(flag)for(auto x:dcc[i])choose[x]=1;//v-DCC中不存在奇环 } for(int i=1 ;i<=n;i++)if(!choose[i])ans++; cout<<ans<<endl; } return 0; }
