题意

https://vjudge.net/problem/CodeForces-1228D

有一个n个顶点m条边的无向图，在一对顶点中最多有一条边。

设v1，v2是两个不相交的非空子集，当满足以下条件时f（v1，v2）为真

v1中的点之间不存在边
v2中的点之间不存在边
对于在v1v2中的每一对顶点，x在v1中，y在v2中，xy之间有边

所有点集不为空，且不相交，是否有v1，v2，v3使得f（v1，v2）、f（v2，v3）、f（v3，v1）均为真

如果有输出每个点所在的点集（1,2,3），否则输出-1

思路

这题比赛没敢开，其实就是个乱搞题，只不过细节很多。。

主要思路就是先随便选一个点插入第一个集合，然后和这个点直接相连的点肯定不能插入第一个集合，不相连的点插入第一个集合。再在不在第一个集合的点中随便选一个点，类似的扩展下去只不过要注意不能用集合1中的点，这样第二个集合就构造好了，剩余的点插入第三个集合，最后判断两两集合是否每个点都相连。这里用map<int,int> mp[N]判断是否相连比较舒服~

代码

#include<bits/stdc++.h>

using namespace std;

#define inf 0x3f3f3f3f

#define ll long long

const int N=200005;

const int mod=1e9+7;

const double eps=1e-8;

const double PI = acos(-1.0);

#define lowbit(x) (x&(-x))

vector<int> g[N];

unordered_map<int,int> mp[N];

int q[N];

int main()

{

    std::ios::sync_with_stdio(false);

    int n,m,flag=0;

    cin>>n>>m;

    for(int i=1; i<=m; i++)

    {

        int u,v;

        cin>>u>>v;

        g[u].push_back(v);

        g[v].push_back(u);

        mp[u][v]=mp[v][u]=1;

    }

    if(m==0)

    {

        cout<<-1<<endl;

        return 0;

    }

    set<int> a,b,c;

    map<int,int> t;

    a.insert(1);

    int sz=g[1].size(),bb;

    if(sz==0)

    {

        cout<<-1<<endl;

        return 0;

    }

    for(int i=1; i<=n; i++)

    {

        if(!mp[1][i])

            a.insert(i);

        else

            bb=i;

    }

    if(a.size()==n)

    {

        cout<<-1<<endl;

        return 0;

    }

    sz=g[bb].size();

    if(sz==0)

    {

        cout<<-1<<endl;

        return 0;

    }

    b.insert(bb);

    for(int i=1; i<=n; i++)

    {

        if(!mp[bb][i]&&a.find(i)==a.end())

        {

            b.insert(i);

        }

    }

    for(int i=1; i<=n; i++)

    {

        if(a.find(i)==a.end()&&b.find(i)==b.end())

        {

            c.insert(i);

        }

    }

    for(int i:a)

    {

        for(int j:b)

        {

            if(!mp[i][j])

            {

                flag=1;

                break;

            }

        }

        for(int j:c)

        {

            if(!mp[i][j])

            {

                flag=1;

                break;

            }

        }

        if(flag)

            break;

    }

    for(int i:b)

    {

        for(int j:c)

        {

            if(!mp[i][j])

            {

                flag=1;

                break;

            }

        }

    }

    if(a.size()+b.size()+c.size()!=n||

            a.size()==0||b.size()==0||c.size()==0||a.size()*b.size()+a.size()*c.size()+b.size()*c.size()!=m)

        flag=1;

    if(flag)

    {

        cout<<-1<<endl;

    }

    else

    {

        for(int i:a)

            q[i]=1;

        for(int i:b)

            q[i]=2;

        for(int i:c)

            q[i]=3;

        for(int i=1; i<=n; i++)

            cout<<q[i]<<" ";

        cout<<endl;

    }

    return 0;

}

巴特西

CodeForces - 1228D （暴力+思维+乱搞）

题意

思路

代码

最新文章

热门文章