建个企业网站需要多少钱,视觉创意设计公司,免费微信微网站模板下载不了,公司做网站的目的J. Burnished Security Updates
题意#xff1a;对于所给的图#xff08;不一定连通#xff09;#xff0c;选择一些点作为一个集合#xff0c;满足每条边有且仅有一个端点为该集合的点#xff0c;要求计算该集合大小的最小可能#xff0c;若无法找到一个集合满足条件则…J. Burnished Security Updates
题意对于所给的图不一定连通选择一些点作为一个集合满足每条边有且仅有一个端点为该集合的点要求计算该集合大小的最小可能若无法找到一个集合满足条件则输出 -1
思路由「每条边有且仅有一个端点为该集合的点」的性质联想到二分图二部图 的性质。采用判断二分图的染色算法其中所用次数较少的颜色数即为我们所需的结果而对于不连通的图则取每个连通部分所用次数较少的颜色数。若中途判断无法构成二分图即说明找不到题目描述的集合输出 -1 即可。
相关链接 判断二分图 - LeetCode
#includebits/stdc.h
using namespace std;const int N 3e510;
vectorint g[N];
int color[N];
int cnt_color[2];
bool dfs(int v, int c)
{if(color[v] ! -1) return color[v] c;color[v] c; cnt_color[c];for(int i 0; i g[v].size(); i){if(!dfs(g[v][i], !c)) return false;}return true;
}
int main()
{int n,m;cinnm;int v1,v2;for(int i 0; i m ; i){scanf(%d%d,v1,v2);g[v1].push_back(v2);g[v2].push_back(v1);}for(int i 1; i n; i) color[i] -1;int ans 0;for(int i 1; i n; i){if(color[i] -1){cnt_color[0] cnt_color[1] 0;if(!dfs(i,0)){ans -1;break;}ans min(cnt_color[0], cnt_color[1]);}}coutans\n;
}
