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;
}