Skip to content

14087: 【原4087】日天部落

题目

题目描述

author: SupremeT 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4087

Description

在遥远的部落,生活着n位骁勇善战的勇士(编号1~n)。他们从一出生,就被赋予了光荣的战斗使命:日天! 同时,这个部落中的人们非常注重战友情谊,若如果A和B共同日过天,那么他们就被认为是战友。 为了评价部落的团结程度,部落酋长吴章引进了评价标准:对于A,B,C三人,如果A和B共同日过天,B和C共同日过天,一定有A和C共同日过天的话,就认为部落是团结的。 在历史上,一共有过m场日天的战斗(每场战斗有且仅有两人参加),也就是说,一共有m对战士共同日过天。 注意,不能认为自己和自己共同日过天。 请你帮帮吴章酋长,看看他的部落是不是团结的吧!

Input Format

输入数据包括

第1行:2个数值, n(战士的人数),m(战斗的场数)

第2~m+1行:两个数值,代表两位共同日过天的战士编号(注意,不存在参加战士编号完全一样的战斗)

Output Format

一行:如果是团结的,输出YES,否则输出NO

Sample Input1

``` 4 3 1 3 3 4 1 4

Sample Output1

YES

Sample Input2

4 4 3 1 2 3 3 4 1 2

Sample Output2

NO

数据范围

3 ≤ n ≤ 150 000, 0 < m < min(150000, n(n - 1) / 2)

FineArtz's solution

/* 日天部落 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

class Point{
public:
    int x = 0;
    int y = 0;
};
bool cmp(Point p1, Point p2){
    return (p1.x < p2.x || p1.x == p2.x && p1.y < p2.y);
}

Point p[150005], pos[150005];
bool v[150005] = {0};
int n, m;

bool bfs(int st){
    queue<int> q;
    q.push(st);
    v[st] = true;
    int now, next;
    int person = 1, battle = 0;
    while (!q.empty()){
        now = q.front();
        q.pop();
        for (int k = pos[now].x; k <= pos[now].y; ++k){
            if (k == 0) break;
            next = p[k].y;
            ++battle;
            if (v[next]) continue;
            ++person;
            q.push(next);
            v[next] = true;
        }
    }
    return (battle == person * (person - 1) / 2);
}
int main(){
    cin >> n >> m;
    memset(v, 0, sizeof(v));
    for (int i = 1; i <= m; ++i){
        cin >> p[i].x >> p[i].y;
        if (p[i].x > p[i].y){
            int t = p[i].x;
            p[i].x = p[i].y;
            p[i].y = t;
        }
    }
    sort(p + 1, p + m + 1, cmp);
    pos[p[1].x].x = 1;
    for (int i = 2; i <= m; ++i){
        if (p[i].x != p[i - 1].x){
            pos[p[i - 1].x].y = i - 1;
            pos[p[i].x].x = i;
        }
    }
    pos[p[m].x].y = m;
    for (int i = 1; i <= m; ++i){
        if (!v[i]){
            bool flag = bfs(i);
            if (!flag){
                cout << "NO" << endl;
                return 0;
            }
        }
    }
    cout << "YES" << endl;
    return 0;
}

WashSwang's solution

#include <cstdio>
using namespace std;
int p[200000],fa[200000],num[200000],n,m,x,y;
int root(int x)//并查集 路径压缩
{
    if (fa[x]==0) return x;
    else return fa[x]=root(fa[x]);
}
void unionset(int x,int y){
    int s=root(x),t=root(y);
    if (s!=t)
    {
        fa[s]=t;
        num[t]+=num[s];//两个集合合并 数量相加
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i){num[i]=1;}
    for (int i=0;i<m;++i)
    {
        scanf("%d%d",&x,&y);
        unionset(x,y);
        p[x]++;
        p[y]++;
    }
    for (int i=1;i<=n;++i)
    {
        if (p[i]!=num[root(i)]-1)
            {
                printf("NO");
                return 0;
            }
    }
    printf("YES");
    return 0;
}