宣传部肖同学

宣传部肖同学

时间： 1ms        内存：128M

描述：

肖同学编程非常厉害，第十届 ACM 省赛肖同学和超超组队成了冠军队伍，肖同学对“超超说自己女装，但是不女装”非常不满，肖同学就告诉了他的好朋友，好朋友又告诉了其他好朋友，问一共有多少同学知道超超要女装。

输入：

输入第一行包含两个整数 n, m，n 是同学的个数，同学编号 1 2 3......n，肖同学是1号，接下来是 m 行输入，每行输入两个数 a b 代表 a b 是好朋友。
其中 2<=n<=500, 1<=m<=500

输出：

输出一共有多少同学知道超超要女装。

示例输入：

4 5
1 2
2 3
1 3
3 2
1 2

示例输出：

3

提示：

参考答案（内存最优[2024]）：

#include<iostream>
using namespace std;
int h[501];
int find(int i){
	if(h[i]!=i)
		return find(h[i]);
	return i;
}
int main(){
	int  a,b,n,m,all=0;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
		h[i]=i;
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&a,&b);
		int ta=find(a);
		int tb=find(b);
		if(ta!=tb)
			h[tb]=ta;
	}
	for(int i=1;i<=n;i++)
	{
		if(find(i)==find(1))
			all++;
	}
	cout<<all;
}

参考答案（时间最优[4]）：

#include <bits/stdc++.h>
#define IO                       \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define mem(a, x) memset(a, x, sizeof(a))
#define per(x, a, b) for (int x = a; x <= b; x++)
#define rep(x, a, b) for (int x = a; x >= b; x--)
 
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const double eps = 1e-8;
 
struct node {
    int from;
    int to;
    int next;
    int cost;
} edge[maxn << 1];
int head[maxn], tot;
 
void init() {
    memset(head, -1, sizeof(head));
    tot = 0;
}
 
void addedge(int u, int v, int cost) {
    edge[tot].from = u;
    edge[tot].to = v;
    edge[tot].cost = cost;
    edge[tot].next = head[u];
    head[u] = tot++;
}
int n, m;
 
bool vis[maxn];
 
void dfs(int x, int fa) {
    if (vis[x])
        return;
    vis[x] = true;
    for (int i = head[x]; i != -1; i = edge[i].next) {
        int to = edge[i].to;
        if (to == fa)
            continue;
        dfs(to, x);
    }
}
void solve() {
    mem(vis, 0);
    dfs(1, -1);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (vis[i])
            ++ans;
    }
    cout << ans << endl;
}
int main() {
#ifdef LOCAL_IM0QIANQIAN
    freopen("test.in", "r", stdin);
//    freopen("test.out", "w", stdout);
#else
    IO;
#endif // LOCAL_IM0QIANQIAN
 
    init();
    cin >> n >> m;
    assert(n <= 500);
    assert(n >= 2);
    assert(m >= 1);
    assert(m <= 500);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        addedge(x, y, 0);
        addedge(y, x, 0);
    }
    solve();
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。