CodeForces 771A Bear and Friendship Condition 【并查集/DFS】

题目大意：

给出n个点，m条边构成的一个无向图。问是否图中所有的边都满足：当a和b相连、b和c相连时，a和c也相连。

解题思路：

当满足上述条件时就说明这k个点构成了一个无向完全图，这种图的充要条件是：边数 = 点数 * (点数 - 1) / 2。
根据这个突破点用DFS搜或者并查集判都可以了。

Mycode(并查集):

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 150010;

int f[N];
long long t[N], e;
void init()
{
    for(int i = 1; i < N; ++i)
        f[i] = i;
}
int Find(int v)
{
    if(f[v] != v)
        f[v] = Find(f[v]);
    return f[v];
}
void Union(int u, int v)
{
    int t1 = Find(u);
    int t2 = Find(v);
    if(t1 != t2)
        f[t2] = t1;
}
int main()
{
    init();
    int n, m; scanf("%d%d",&n,&m);
    for(int i = 0; i < m; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        Union(u, v);
    }
    for(int i = 1; i <= n; ++i)
    {
        ++t[Find(i)];
    }
    for(int i = 1; i <= n; ++i)
    {
        if(t[i])
            e += t[i] * (t[i] - 1) / 2;
    }
    puts(e == m ? "YES" : "NO");
    return 0;
}

Mycode(DFS):

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int M = 150010;

bool vis[M];
vector<int> G[M];
int n, m, x, y, v, e;
void DFS(int t, int & v, int & e)
{
    vis[t] = true;
    ++v;
    e += G[t].size();
    for(int i = 0; i < G[t].size(); ++i)
        if(!vis[G[t][i]])
            DFS(G[t][i], v, e);
}
int main()
{
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i = 1; i <= n; ++i)
    {
        if(!vis[i])
        {
            v = e = 0;
            DFS(i, v, e);
            if(e != 1ll * v * (v - 1))
            {
                puts("NO");
                return 0;
            }
        }
    }
    puts("YES");
    return 0;
}