比赛 欢乐五一练练练 评测结果 AAAAAAAAAA
题目名称 宗教信仰 最终得分 100
用户昵称 sxysxy 运行时间 1.056 s
代码语言 C++ 内存使用 1.07 MiB
提交时间 2017-04-26 19:21:24
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cctype>
using namespace std;
int fast_read()
{
    int r;
    bool sig = false;
    char ch;
    while(ch = getchar())
    {
        if(ch >= '0' && ch <= '9')
        {
            r = ch^0x30;
            break;
        }else if(ch == '-')sig = true;
    }
    while(isdigit(ch = getchar()))
        r = (r<<3)+(r<<1)+(ch^0x30);
    return sig? -r:r;
}
#define MAXN 50001
vector<int> G[MAXN];
int uid[MAXN];
void dfs(int u, int f, int b)
{
    if(uid[u])return;
    uid[u] = b;
    for(int i = 0; i < G[u].size(); i++)
        if(G[u][i] != f)dfs(G[u][i], u, b);
}
int main()
{
    freopen("religion.in", "r", stdin);
    freopen("religion.out", "w", stdout);
    int n, m;
    n = fast_read();
    m = fast_read();
        while(m--)
        {
            int x, y;
            x = fast_read();
            y = fast_read();
            G[x].push_back(y);
            G[y].push_back(x);
        }
        int gg = 0;
        for(int k = 1; k <= n; k++)
            if(!uid[k])dfs(k, 0, ++gg);
        printf("%d\n", gg);
    return 0;
}