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

### 题目描述

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

## Sample Input 1

1
4 2
1 2
2 3


## Sample Output 1

1


## Sample Input 2

1
3 3
1 2
2 3
1 3


## Sample Output 2

-1


## 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;
edg[cnt] = v;
}

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(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);
}
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 t,m,n,u,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);
}
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;
}