14130: 【原4130】This is a NP-Hard Problem

题目描述

author: Lmxyy 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4130

Description

最近dhh带着xyy对NP-Hard问题进行了一些研究，他们发现最小点覆盖问题特别有趣。

所谓点覆盖，即给你一张图\(G(V,E)\)和他的一个点集\(A\)。如果对于\(G\)中的任何一条边\(u,v\)，都要么有\(u \in A\)或者\(v \in A\)，则\(A\)称为\(G\)的一个点覆盖。

由于dhh打乒乓球太腻害了，所以他赢得了一张\(N\)个点\(M\)条边的无向图，现在他准备把图中的点分成不相交的两份，拿出来一份送给xyy。xyy欣然接受，但他希望他所得到点是原图中的一个点覆盖；dhh同时也希望他留下的那份是原图中一个点覆盖。

现在他们想知道是否存在这样一种分法，能够同时满足两个人的要求。

Input Format

第一行一个正整数\(T\)，表示数据组数。

对于每组数据，第一行两个正整数\(N\)和\(M\)，意义如题意。

接下来\(M\)行，每行两个正整数\(u,v\)，表示图中的一条边。

Output Format

每组数据各输出一行，\(1\)表示可以满足两人要求，\(-1\)表示无法满足要求。

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

-1

Data Range

对于\(30 \%\)的数据，\(N \le10 \)，\(M \le 20\)。

对于\(60 \%\)的数据，\(N \le1000 \)，\(M \le 2000\)。

对于\(100 \%\)的数据，\(2 \le N \le 100000\)，\(0 \le M \le 200000\)，\(T = 10\)。点的编号以\(1\)开始。

Hint

若果遇到莫名其妙tle，请关闭同步或改用scanf读入。

FineArtz's solution

/* This is a NP-Hard Problem */
#include <cstdio>
#include <cstring>
using namespace std;

int n, m;
int be[100005], head[100005], nxt[400005], edg[400005], cnt;

inline void addEdge(int u, int v){
    ++cnt;
    nxt[cnt] = head[u];
    edg[cnt] = v;
    head[u] = cnt;
}

bool check(int st){
    int q[100005] = {0};
    int front = 0, rear = 0;
    be[st] = 1;
    q[rear++] = st;
    while (front != rear){
        int now = q[front++];
        for (int i = head[now]; i; i = nxt[i]){
            if (be[edg[i]] == 0){
                int v = edg[i];
                be[v] = (be[now] == 1 ? -1 : 1);
                q[rear++] = v;
            }
            else if (be[edg[i]] != -be[now])
                return false;
        }
    }
    return true;
}

int main(){
    int t;
    scanf("%d", &t);
    while (t--){
        scanf("%d%d", &n, &m);
        memset(be, 0, sizeof(be));
        memset(head, 0, sizeof(head));
        memset(nxt, 0, sizeof(nxt));
        memset(edg, 0, sizeof(edg));
        cnt = 0;
        for (int i = 1; i <= m; ++i){
            int u, v;
            scanf("%d%d", &u, &v);
            addEdge(u, v);
            addEdge(v, u);
        }
        bool flag = true;
        for (int i = 1; i <= n; ++i){
            if (head[i] != 0 && be[i] == 0){
                if (!check(i)){
                    flag = false;
                    printf("-1\n");
                    break;
                }
            }
        }
        if (flag)
            printf("1\n");
    }
    return 0;
}

WashSwang's solution

#include <cstdio>
#include <cstring>
using namespace std;
int ne[400010],to[400010],last[400010],num,k[400010],tail,head,ans;
int t,m,n,u,v;
void add(int u,int v)
{
    ne[++num]=last[u];
    to[num]=v;
    last[u]=num;
}
int dfs(int x)
{
    for (int i=last[x];i!=0;i=ne[i])
    {
        if (!k[to[i]])
        {
            k[to[i]]=-k[x];
            if (!dfs(to[i])) return 0;
        }
        else
            if (k[to[i]]+k[x]!=0)
                return 0;
    }
    return 1;
}
int main() {
    scanf("%d",&t);
    for (int i=0;i<t;++i) {
        scanf("%d%d", &n, &m);
        num=0;
        memset(last, 0, sizeof(last));
        memset(k, 0, sizeof(k));
        for (int j = 0; j < m; ++j) {
            scanf("%d%d", &u, &v);
            add(u,v);
            add(v,u);
        }
        ans=1;
        for (int j=1;j<=n;++j)
            if (k[j]==0){
                k[j]=1;
                if (!dfs(j))
                {
                    ans=-1;
                    break;
                }
            }
        printf("%d\n",ans);
    }
    return 0;
}