poj 2942 Knights of the Round Table(补图的求取+双连通分量+奇环的判断)_求补图的没有奇环的点双连通飞亮-程序员宅基地

技术标签: 点双连通分量  图论  tarjan  割点  

题目链接:

点击打开链接

题目大意:

给出一些骑士,他们之间有的人相互厌恶,不能挨着坐,如果一个骑士不能在任何一个奇环中出现,那么他要被剔除,问最少踢掉多少骑士

题目分析:

首先我们这些骑士要围成一个环,我们知道一个点双连通分量的任意两条边都在同一个简单环上,所以我们将厌恶关系连边,然后求补图,求出补图中的所有的点双连通分量,判断奇环通过染色法,也就是只要在深搜过程中碰到两个相邻的点颜色相同,那么就是奇环,对于每个点双连通分量,只要点双连通分量中存在奇环,那么就一定能够保证该点双连通分量中的骑士都能顺利开上会。而点双连通分量可以通过割点求出,dfs中割点下的部分一定是一个点双通分量,而且是以该割点相连的点为栈顶元素的

代码如下:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

#define MAXp 1009
#define MAXe 1000009
using namespace std;

struct
{
    int v;
    int next;
}e[ MAXe*2 ];

int head[MAXp],dfn[MAXp],low[MAXp],ts,c,stk[MAXp],r,s,in[MAXp],cnt,color[MAXp],n;
bool mp[MAXp][MAXp],flag[MAXp];

void add ( int u , int v )
{
    e[c].v = v;
    e[c].next = head[u];
    head[u] = c++;
}

//利用染色法判断一个双连通分量是否为一个奇环
bool paint ( int u , int y , int pre )
{
    int i,v;
    color[u]= y;
    for ( i = head[u]; i!=-1; i = e[i].next )
    {
        v =e[i].v;
        if ( in[v] == 1 && v != pre )
        {
            if ( color[v] == -1 )
            {
                if ( paint( v , color[u]^1 , u )) return true;
            }
            else if ( color[u] == color[v] ) return true;
        }
    }
    return false;
}

//利用tarjan求解各个点双连通分量,只要被验证时奇环的点双连通分量的点就能够参加至少一次会议
//点双连通分量中的点都在一个简单环中
void dfs ( int u , int pre )
{
    int i,j,v;
    dfn[u] = low[u] = ++ts;
    stk[++s] = u;
    for ( i = head[u] ; i != -1 ; i = e[i].next )
    {
        v = e[i].v;
        if ( !dfn[v] )
        {
            dfs ( v ,u );
            low[u] = min ( low[u],low[v]);
            //求割点,利用割点划分出点双连通分量
            if ( dfn[u] <= low[v] )
            {
                memset ( in , 0 , sizeof (in));
                in[u] = 1;
                while ( stk[s] != v )
                {
                    in[stk[s]]=1;
                    s--;
                }
                in[v] = 1;
                s--;
                memset (color,-1,sizeof(color) );
                if ( paint(u , 1 , -1 ) )
                {
                    for (j =1 ; j <= n ; j++ )
                        if ( in[j] == 1 ) flag[j]=true;
                }
            }
        }
        else if ( v != pre ) low[u] = min ( low[u] , dfn[v] );
    }
}

int main ( )
{
    int m,u,v,i,j,ans;
    while ( scanf ("%d%d" , &n , &m ) )
    {
        if ( !n && !m ) break;
        memset ( mp ,false , sizeof(mp) );
        //构造补图
        for ( i = 0 ; i <m ; i++)
        {
            scanf ( "%d%d" , &u , &v );
            mp[u][v] = mp[v][u] = true;
        }
        c =0;
        memset ( head , -1 , sizeof(head) );
        for ( int i = 1 ; i <= n ; i++ )
            for ( int j = i +1 ; j <= n ; j++)
                if ( !mp[i][j])
                {
                    add ( i ,j );
                    add ( j ,i );
                }

        ts =0;
        s = -1;
        memset ( dfn , 0 , sizeof( dfn ) );
        memset ( flag , false , sizeof(flag ) );
        //给出的图不一定是连通图
        for ( i =1 ; i <= n ; i++ )
            if ( !dfn[i] ) dfs ( i , -1 );
        ans = 0;
        //不在任何一个奇环中的点需要被淘汰
        for ( i =1 ; i <= n ; i++ )
            if ( !flag[i] ) ans++;
        printf ( "%d\n" , ans );
    }
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_24451605/article/details/46889895

智能推荐

微信小程序学习笔记-scroll-view中的enable-flex、 scroll-y、 scroll-x 无效_unknown property: 'text-wrap-程序员宅基地

文章浏览阅读742次。解决方法在scroll-view的样式中加上:white-space: nowrap;在scroll-view的子标签的样式加上:_unknown property: 'text-wrap

error LNK2001: 无法解析的外部符号 __imp__MessageBoxA@16_error lnk2001: 无法解析的外部符号 __imp__mcisendcommanda@16-程序员宅基地

文章浏览阅读7.2k次。错误:error LNK2001: 无法解析的外部符号 __imp__MessageBoxA@16原因:本来程序的编译选项选择的是:使用标准windows库,当改为在静态库中使用MFC后就出现了上面的错误解决方法代码中添加依赖库#pragma comment(lib,"User32.lib")_error lnk2001: 无法解析的外部符号 __imp__mcisendcommanda@16

easyUI之可拖动控件——easyui-draggable_easyui draggable handle什么意思-程序员宅基地

文章浏览阅读1.4k次。本文章取自51CTO视频,仅供学习参考。_easyui draggable handle什么意思

linux /etc 下的文件总结_linux /etc/apt 下文件介绍-程序员宅基地

文章浏览阅读545次。1. /etc/fstab就是在开机引导的时候自动挂载到linux的文件系统。 在linux中/etc/fstab的数据项如下所示:/dev/device mountpoint type rules 0 order 例如这是一个普通的/etc/fstab:/dev/hda2 / ext3 defaults 0 1/dev/hda3 swap swap defaults 0_linux /etc/apt 下文件介绍

用于Delphi的VCL组件DevExpress VCL正式发布v20.2.8_devexpress vcl 20下载-程序员宅基地

文章浏览阅读364次。DevExpress VCL Controls是Devexpress公司旗下最老牌的用户界面套包,所包含的控件有:数据录入、图表、数据分析、导航、布局等。该控件能帮助您创建优异的用户体验,提供高影响力的业务解决方案,并利用您现有的VCL技能为未来构建下一代应用程序。DevExpress VCL v20.2.8最新版下载DevExpress技术交流群3:700924826欢迎一起进群讨论具体更新内容如下:此列表包括v20.2.8中已解决的所有问题。ExpressBars Sui..._devexpress vcl 20下载

g2o图优化库入门介绍_g2o chi2-程序员宅基地

文章浏览阅读1.3k次,点赞3次,收藏17次。g2o图优化库的使用1、背景知识介绍2、代码详解一、点和边的类型定义二、构建图优化实例,配置求解器三、添加点和边四、执行优化3、ax^2+bx+c实现一、程序:二、运行结果1、背景知识介绍优化的目的是为了通过当前已知的系统理想化的模型和实际测量的数据获取最近接真实值的系统结果。这样的定义让人很容易联想起来各种滤波方法的目的,的确滤波方法和图优化方案解决的问题都是对不可靠的测量值进行处理以获取尽可能接近真实值的结果,例如以卡尔曼滤波器为例,在进行操作之前我们需要有一个相对靠谱的预测模型用来获取先验(预测)_g2o chi2

随便推点

Python干旱指数库climate_indices学习-程序员宅基地

文章浏览阅读3k次。Githubclimate_indices库能够计算的指数如下:SPI,Standardized Precipitation Index, 标准化降水指数,utilizing both gamma and Pearson Type III distributionsSPEI,Standardized Precipitation Evapotranspiration Index,标准化降水蒸散指数,utilizing both gamma and Pearson Type III distribu_python干旱指数库climate_indices

格兰杰检验的基本步骤_Toda-Yamamoto 格兰杰因果检验 TY-Granger方法-程序员宅基地

文章浏览阅读6.2k次。一、格兰杰因果关系定义对于因变量,找到有助于预测的协变量。"X is said to Granger-causeY if Y can be better predicted using the histories of bothX and Y than it can by using the history of Y alone."二、格兰杰因果检验格兰杰因果检验本质是对VAR模型的参数进行线性..._格兰杰因果检验步骤

arcpy删除GDB文件_arcpy delete gdb-程序员宅基地

文章浏览阅读2k次。此前做的工作是将GDB里面的文件遍历删除再重新创建def deleteGDBFile(gdbpath): env.workspace=gdbpath fcs=arcpy.ListFeatureClasses() for fc in fcs: arcpy.Delete_management(fc) fcs = arcpy.ListTables()..._arcpy delete gdb

string[] array arrayList hashtable list<> dictionary<,> 数组、集合、泛型集合_array arraylist hashtable-程序员宅基地

文章浏览阅读1.1k次。数组 à 集合 à 泛型集合 写法说明数组Int[] arrInt;固定大小,固定元素类型集合arrayListhashtable SortedList可变长度Object类型泛型集合ListDiction_array arraylist hashtable

postgis JDBC_postgis-jdbc jar包-程序员宅基地

文章浏览阅读2.1k次。postgis进行jdbc连接时,应在classpath和项目对应的WEB-INF/lib下同时引入jar包,否则就会找不到具体连接代码为:Connection c = null; Statement stmt = null; try { Class.forName("org.postgresql.Driver");_postgis-jdbc jar包

Vue3 + Vite + Ts 获取dom(通过ref)_vite 获取元素-程序员宅基地

文章浏览阅读2.8k次,点赞2次,收藏3次。元素上ref和 Vue2 一样: <div class="classfy_cell flex j-a a-c" ref="classfy">获取dom<script setup lang="ts"> import { getCurrentInstance, onMounted } from "vue"; // 引入全局 let refs = null; onMounted(() => { let { $refs } =_vite 获取元素

推荐文章

热门文章

相关标签