思路:建补图-割点-点双连通图-判奇环-输出
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e3+5,inf=1<<29;
const double eps=1e-6;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
struct Edge{ int ver,next;}edge[maxn*maxn/2];
int n,m,tot,head[maxn],link[maxn][maxn],root,dfn[maxn],low[maxn],
Stack[maxn],num,top,cnt,c[maxn],res[maxn],vis[maxn];
vector<int> dcc[maxn];
void add(int u,int v) {
edge[++tot].ver=v; edge[tot].next=head[u]; head[u]=tot;
}
void tarjan(int x){
dfn[x]=low[x]=++num;
Stack[++top]=x;
if(x==root&&head[x]==0) {
dcc[++cnt].push_back(x);
return ;
}
for(int i=head[x],y;i;i=edge[i].next) {
if(!dfn[y=edge[i].ver]) {
tarjan(y);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
int z; cnt++;
do{
z=Stack[top--];
dcc[cnt].push_back(z);
} while(z!=y);
dcc[cnt].push_back(x);
}
} else low[x]=min(low[x],dfn[y]);
}
}
bool dfs(int x,int color) { //二分图判定奇环
vis[x]=color;
for(int i=head[x],y;i;i=edge[i].next) {
if(c[y=edge[i].ver]==c[x]) {
if(!vis[y]) {
if(dfs(y,3-color)) return 1; //传递出结果
}
else if(vis[y]==color) return 1;
}
} return 0;
}
void init() {
tot=top=num=cnt=0;
memset(link,0,sizeof(link));
memset(head,0,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(res,0,sizeof(res));
memset(c,0,sizeof(c));
}
//建补图-割点-点双连通图-判奇环-输出
int main(){
ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
while(cin>>n>>m,n||m){
init();
while(m--) { //记录边
int a,b; cin>>a>>b;
link[a][b]=link[b][a]=1;
} //建图
for(int i=1;i<n;++i){
for(int j=i+1;j<=n;j++) {
if(link[i][j]==0)
add(i,j),add(j,i);
}
} //割点+点双连通分量
for(int i=1;i<=n;i++) {
if(!dfn[i]) tarjan(i);
} //判奇环
for(int i=1;i<=cnt;i++) {
if(dcc[i].size()>1){
for(int j=0;j<dcc[i].size();j++){
c[dcc[i][j]]=i; //边双连通图块号
}
memset(vis,0,sizeof(vis));
if(dfs(dcc[i][0],1)) {
for(int j=0;j<dcc[i].size();j++)
res[dcc[i][j] ]= 1 ; //可以加入会议
}
}
dcc[i].clear(); //清空数据
} int ans=0;
for(int i=1;i<=n;i++) {
if(res[i]==0) ans++;
} cout<<ans<<'\n';
}
return 0;
}