首页 > 其他分享 >CF805(div3)E. Split Into Two Sets

CF805(div3)E. Split Into Two Sets

时间:2022-08-17 22:46:15浏览次数:101  
标签:return int Into Two color mp false include Split

Problem - 1702E - Codeforces

思路:这道题自己没磕出来思路,大体上就是,先将节点相互连接起来,{1,2}{2,1},{3,4}{4,3}当形成的环是偶数的时候,既可以间隔选择形成二分图,若能形成二分图,则两边选择的多米诺牌都是独立的,如果不能形成二分图,那么证明多米诺牌出现了重复现象。

输入的时候特判自环,还有特判一下每个数字是否出现超过两次

Solution:  

/*
 *                                |~~~~~~~|
 *                                |       |
 *                                |       |
 *                                |       |
 *                                |       |
 *                                |       |
 *     |~.\\\_\~~~~~~~~~~~~~~xx~~~         ~~~~~~~~~~~~~~~~~~~~~/_//;~|
 *     |  \  o \_         ,XXXXX),                         _..-~ o /  |
 *     |    ~~\  ~-.     XXXXX`)))),                 _.--~~   .-~~~   |
 *      ~~~~~~~`\   ~\~~~XXX' _/ ';))     |~~~~~~..-~     _.-~ ~~~~~~~
 *               `\   ~~--`_\~\, ;;;\)__.---.~~~      _.-~
 *                 ~-.       `:;;/;; \          _..-~~
 *                    ~-._      `''        /-~-~
 *                        `\              /  /
 *                          |         ,   | |
 *                           |  '        /  |
 *                            \/;          |
 *                             ;;          |
 *                             `;   .       |
 *                             |~~~-----.....|
 *                            | \             \
 *                           | /\~~--...__    |
 *                           (|  `\       __-\|
 *                           ||    \_   /~    |
 *                           |)     \~-'      |
 *                            |      | \      '
 *                            |      |  \    :
 *                             \     |  |    |
 *                              |    )  (    )
 *                               \  /;  /\  |
 *                               |    |/   |
 *                               |    |   |
 *                                \  .'  ||
 *                                |  |  | |
 *                                (  | |  |
 *                                |   \ \ |
 *                                || o `.)|
 *                                |`\\) |
 *                                |       |
 *                                |       |
 */
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<unordered_map>
#include<map>
// #pragma GCC optimize(3)
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define scan(x)   scanf("%lld",&x)
#define int long long
#define lowbit(x) x&(-x) //二进制最低位所代表的数
#define PI 3.1415926535
typedef pair<int,int> PII;
int gcd(int a,int b){
    return b>0 ? gcd(b,a%b):a;
}
int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x = 1,y = 0;
        return a;
    }
    int d = exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
const int N = 2e5+10;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;
void init()
{
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(false);
}

map<int,vector<int>> mp;

int color[N];

bool dfs(int u,int c)
{
    color[u]=c;
    for(auto j:mp[u])
    {
        if(!color[j])
        {
            if(!dfs(j,3-c))return false;
        }else if(color[j]==c)return false;
    }
    return true;
}
void solve()
{
    mp.clear();
    memset(color,0,sizeof color);
    int n;
    cin>>n;
    bool flag = true;
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        mp[x].push_back(y);
        mp[y].push_back(x);
        if(x==y||mp[x].size()>2||mp[y].size()>2)
        {
            flag = false;
        }
    }
    if(!flag)
    {
        cout<<"NO"<<endl;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!color[i])
        {
            if(!dfs(i,1))
            {
                cout<<"NO"<<endl;
                return;
            }
        }
    }
    cout<<"Yes"<<endl;
}

signed main()
{
    init();
    int t;
    cin>>t;
    while(t--)solve();
}
View Code

 

标签:return,int,Into,Two,color,mp,false,include,Split
From: https://www.cnblogs.com/yeonnyuui/p/16597040.html

相关文章

  • split() 方法
    split()方法根据匹配给定的正则表达式来拆分字符串。注意:.、$、|和*****等转义字符,必须得加\\。注意:多个分隔符,可以用|作为连字符。语法:publicString[]s......
  • 【CV源码项目实现】darknet中network的实现过程
     darknet的网络结构使用network结构体进行保存,network的构建过程主要包括以下几个函数:load_network(src/networks.c)----->parse_network_cfg(src/parser.c) --->ma......
  • 关于在 debian 里被 network-tools 托管后如何重连 WIFI 的问题。
    ifconfig、ifup、ifdown三个命令。如果修改了/etc/wpa_supplicant/wpa_supplicant.conf后想重连wifi需要强制down了waln0后在ifup就行了。ifdownwlan0--for......
  • Network: use --host to expose
    vite启动后提示:Network:use --host toexpose,且无法通过网络IP访问服务   原因:当 局域网 中另一台设备需要访问该服务时,必须通过本机 IP+端口 访问。尝......
  • select into
    SELECT INTO 语句从一个表复制数据,然后把数据插入到另一个新表中。MySQL 数据库不支持 SELECT ... INTO 语句,但支持 INSERT INTO ... SELECT 。可使用以下语句......
  • AT ARC092F Two Faced Edges
    题意:给定一个有向图,保证无重边自环,求将图中的每条边反向后强联通分量的个数是否会改变。数据范围:$n$$≤$ $1000$,$m$$≤$$200000$。首先考虑一条边的影响。因为一条......
  • MobaXterm链接linux虚拟机报错Network error: Connection refused
    原文链接使用虚拟机安装Ubuntu,然后在Windows下使用MobaXterm链接。若出现如下报错:Networkerror:Connectionrefused需要安装openssh:sudoaptinstallopens......
  • String _split()
    S.split(s)表示将字符串S按照s截开,对于空白字符Stringstr="abcd";String[]arr1=str.split("");//仅分割一个空格String[]arr2=str.split("s");Strin......
  • CAD绘图软件CADintosh推荐
    很多用户都在使用CAD绘图软件CADintoshXMac版吧?今天来分享CADintoshXforMa版,新增查找并替换线宽,查找并替换组,查找和替换图层,改进的DXF和DWG导入,选项禁用DXF预处理等新......
  • python | split函数时间复杂度
    源码while(maxcount-->0){while(i<str_len&&STRINGLIB_ISSPACE(str[i]))i++;if(i==str_len)break;j=i;i++;while(i<......