列表

详情

NC21887. 有人在说谎吗？

描述

真相永远只有一个，大家都知道ACM界的tokitsukaze大佬喜欢女装，有一天tokitsukaze大佬的女装照片泄露了，已知最开始拥有tokitsukaze大佬的女装照的只有一个人(犯人)并且通过这个人将照片传播开来。害羞的tokitsukaze大佬因此抓捕了一群嫌疑人，这群人内可能没有或者只有一个最初的犯人。并通过逼供知道了这群人之中哪些人拥有照片，哪些人没有照片。然后这些人中部分人拥有一个传播关系——如果他得到照片之后一定会转发给一些自己的熟人，这样这个照片到最后会被“一传十，十传百”。现在tokitsukaze知道这群被抓捕的人里面的每个人传播关系，tokitsukaze想问你在逼供的过程中这些人中有没有人在说谎（没有照片秘密谎称自己有，有照片谎称没照片，我们都认为是在说谎）。默认不存在矛盾就是没有人在说谎，若存在除了给定关系之外的传播关系，那么我们认为是有人在说谎。"不保证没有重边（多次发送照片），或者自环（自己给自己转发一遍）"

输入描述

首先输入一个T，表示T组案例（T<=25）。每组案例先输入两个数字N,M表示有N个人，M个关系（1<=N<=10^5;0<=M<=10^6）。然后一行包含N个bool型数字（0或者1），第i个数字是0代表第i个人不知道秘密，1代表知道秘密。然后M行，每行两个数字P和Q，代表第P个人知道秘密之后一定会告诉第Q个人（1<=P,Q<=N）。人的编号从1开始。

输出描述

输出"yinyinyin"代表有人在说谎，输出"hahaha"代表没人在说谎。

示例1

输入: 

21
1 0
1
1 0
0
2 1
1 1
1 2
2 1
1 0
1 2
2 1
0 1
1 2
7 7
1 1 1 1 1 1 1
1 2
2 3
4 1
2 4
3 4
4 5
5 3
7 7
0 0 0 0 0 0 1
1 2
2 3
4 1
2 4
3 4
4 5
5 3
5 7
1 1 1 1 1
1 2
2 3
4 1
2 4
3 4
4 5
5 3
6 8
1 1 1 1 1 0
1 2
2 3
4 1
2 4
3 4
4 5
5 3
6 1
6 8
1 1 1 1 1 0
1 2
2 3
4 1
2 4
3 4
4 5
5 3
1 6
6 9
1 1 1 0 1 1
1 2
2 3
4 1
2 4
3 4
4 5
5 3
6 1
5 6
6 9
0 0 0 0 0 0
1 2
2 3
4 1
2 4
3 4
4 5
5 3
6 1
5 6
7 10
0 0 0 0 0 0 1
1 2
2 3
4 1
2 4
3 4
4 5
5 3
6 1
5 6
5 7
9 11
0 0 0 1 1 1 0 0 0
1 2
2 3
3 1
3 4
4 5
5 6
6 4
6 7
7 8
8 9
9 7
9 11
0 0 0 1 1 1 1 1 1
1 2
2 3
3 1
3 4
4 5
5 6
6 4
6 7
7 8
8 9
9 7
9 11
0 0 0 0 1 1 1 1 1
1 2
2 3
3 1
3 4
4 5
5 6
6 4
6 7
7 8
8 9
9 7
12 16
1 1 1 1 1 1 1 1 1 0 0 0
1 2
2 3
3 1
3 4
4 5
5 6
6 4
6 7
7 8
8 9
9 7
2 11
10 11
11 12
12 10
12 8
12 16
0 0 0 1 1 1 1 1 1 0 0 0
1 2
2 3
3 1
3 4
4 5
5 6
6 4
6 7
7 8
8 9
9 7
2 11
10 11
11 12
12 10
12 8
4 4
0 0 1 1
1 2
2 1
1 3
2 4
4 4
0 1 1 1
1 2
2 1
1 3
2 4
4 4
1 1 1 1
1 2
2 1
1 3
2 4

输出: 

hahaha
hahaha
hahaha
yinyinyin
hahaha
yinyinyin
hahaha
hahaha
hahaha
yinyinyin
yinyinyin
hahaha
hahaha
yinyinyin
hahaha
yinyinyin
yinyinyin
hahaha
yinyinyin
yinyinyin
hahaha

说明:

样例很强，爱信不信，如果过了这么良心、全面的案例还是WA了，可以考虑是重边或者自环或者一些小细节的处理有问题

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 389ms, 内存消耗: 1160K, 提交时间: 2019-12-18 11:03:08 

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 100100
using namespace std;
int list[maxn];
int par[maxn];
int find(int x) {
	if (par[x] == -1) return x;
	return par[x] = find(par[x]);
}
int n, m;
int unin(int x, int  y) {
	int xx = find(x);
	int yy = find(y);
	if (xx == yy) return 0;
	par[yy] = xx;
	return 0;
}

int main() {
	int be, en;
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d %d", &n, &m);
		memset(par, -1, sizeof(par));
		int ccc = 0;
		for (int i = 1; i <= n; i++) {
			scanf("%d", &list[i]);
			if (list[i]) ccc = 1;
		}

		for (int i = 0; i < m; i++) {
			scanf("%d%d", &be, &en);
			if (list[be]) {
				unin(be, en);
			}
		}
		if (!ccc) {
			printf("hahaha\n");
			continue;
		}
		int root = 0;
		for (int i = 1; i <= n; i++) {
			if (list[i]) {
				root = find(i);
				break;
			}
			
		}

		int flag = 0;
		for (int i = 1; i <= n; i++) {
			if (list[i]) {
				if (find(i) != root) {
					flag = 1;
					break;
				}
			}
			else {
				if (find(i) != i) flag = 1;
			}
		}
		if (flag) printf("yinyinyin\n");
		else printf("hahaha\n");
	}


	


	return 0;
}

C++ 解法, 执行用时: 517ms, 内存消耗: 1284K, 提交时间: 2021-10-20 21:47:00 

#include<bits/stdc++.h>
using namespace std;
int fa[200005];
void init(int n)
{
    for(int i=0;i<=n;i++)
        fa[i]=i;
}
int a[200005];
int find(int x)
{
    if(fa[x]==x)
        return x;
    else
        return fa[x]=find(fa[x]);
}
void join(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if(fa[fx]!=fy)
        fa[fy]=fx;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        init(n);
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int x,y;
        int flag=0;
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y;
            if(a[x]==1&&a[y]==0)
                flag=1;
            if(a[x]==1)
                join(x,y),a[y]=1;
        }
        int num=0;
        for(int i=1;i<=n;i++)
        {
            if(fa[i]==i&&a[i]==1)
                num++;
        }
        if(num>1)
            flag=1;
        if(flag)
            cout<<"yinyinyin"<<endl;
        else
            cout<<"hahaha"<<endl;
    }
    return 0;
}

上一题

© 2024 nowcoder.com