poj 2942 Knights of the Round Table （点双连通分量求解） - c++编程基础

开会议？

注意：1、所给出的憎恨关系一定是双向的，不存在单向憎恨关系。
2、由于是圆桌会议，则每个出席的骑士身边必定刚好有2个骑士。即每个骑士的座位两边都必定各有一个骑士。
3、一个骑士无法开会，就是说至少有3个骑士才可能开会。

思路：

根据所给图构出补图，Tarjan求点双连通分量（用栈保存边），然后用交叉染色法判断是否存在奇圈，有一个结论是双连通分量如果存在一个奇圈，那么这个分量中所有的点都能在某一个奇圈中，这样就不必每个点都判断了。

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
         #include 
         
           #include 
          
            #include 
           
             #include 
            
              #pragma comment (linker,"/STACK:102400000,102400000") #define maxn 1005 #define MAXN 1000005 #define mod 1000000007 #define INF 0x3f3f3f3f #define pi acos(-1.0) #define eps 0.000001 typedef long long ll; using namespace std; int n,m,ans,cnt,tot,flag,sum; int dfn[maxn],low[maxn]; int vis[maxn],app[maxn],ok[maxn]; int edge[maxn][maxn]; int lt[maxn][maxn],xx[maxn]; struct Node { int u,v; } cur,sta[MAXN]; void presolve() { int i,j,t; for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { edge[i][j]^=1; } } } void dfs(int u,int fa) { // printf("%d->",u); int i,j,t,v; if(fa) sta[++cnt].u=u,sta[cnt].v=fa; low[u]=dfn[u]=++tot; for(i=1; i<=n; i++) { if(!edge[u][i]||u==i) continue ; if(vis[i]) { if(i!=fa) low[u]=min(low[u],dfn[i]); } else { vis[i]=1; dfs(i,u); low[u]=min(low[u],low[i]); if(dfn[u]<=low[i]) { sum++; // printf("sum:%d\n",sum); cur=sta[cnt]; while(!(cur.u==u&&cur.v==i||cur.u==i&&cur.v==u)) { lt[sum][cur.u]=lt[sum][cur.v]=1; // printf("%d-%d ",cur.u,cur.v); cnt--; cur=sta[cnt]; } cnt--; lt[sum][u]=lt[sum][i]=1; // printf("%d-%d\n",u,i); } } } } void color(int u,int c,int d) { if(flag) return ; int i,j,t; for(i=1; i<=u; i++) { if(!edge[u][i]||i==u||!app[i]) continue ; if(vis[i]!=-1) { if(vis[i]==c) { flag=1; return ; } } else { vis[i]=c^1; color(i,c^1,d); } } } void solve() { int i,j,t,u,v; memset(vis,0,sizeof(vis)); memset(lt,0,sizeof(lt)); sum=0; for(i=1; i<=n; i++) { if(!vis[i]) { tot=cnt=0; vis[i]=1; dfs(i,0); } } memset(ok,0,sizeof(ok)); for(i=1; i<=sum; i++) { t=0; memset(app,0,sizeof(app)); for(j=1; j<=n; j++) { if(lt[i][j]) { t++,app[j]=1; xx[t]=j; } } // printf("i:%d t:%d\n",i,t); for(j=1; j<=t; j++) { flag=0; memset(vis,-1,sizeof(vis)); vis[xx[j]]=1; color(xx[j],1,i); if(flag) break ; } if(flag) { for(j=1; j<=t; j++) { ok[xx[j]]=1; } } } ans=0; for(i=1; i<=n; i++) { ans+=ok[i]; // printf("i:%d ok[i]:%d\n",i,ok[i]); } ans=n-ans; } int main() { int i,j,t,u,v,w; while(scanf("%d%d",&n,&m),n|m) { memset(edge,0,sizeof(edge)); for(i=1; i<=m; i++) { scanf("%d%d",&u,&v); edge[u][v]=edge[v][u]=1; } presolve(); // 求补图 solve(); printf("%d\n",ans); } return 0; } /* 5 8 3 1 3 5 5 5 4 2 5 3 3 3 4 3 3 4 ans: 1 */

poj 2942 Knights of the Round Table （点双连通分量求解）(二)