cogs 3008. 朋友圈

3008. 朋友圈

★★   输入文件：friendscircle.in   输出文件：friendscircle.out   简单对比
时间限制：1 s   内存限制：256 MB

【题目描述】

NOI班有n位学员，因为相处时间有限，有的学员之间加了微信，有的学员之间没有。假设加微信的关系是相互的，即如果a加了b的微信，b也会加a的微信。

现在有一条NOI班上的爆炸性的新闻从1号学员发出，每个看到这个新闻的NOI班学员都会在朋友圈转发，而加了他微信的朋友都会看到。没有在NOI班上的学员都不会转发（因为和自己关系不大）。

告诉你NOI班上的学员之间的微信好友关系，请问最终有多少个学员看到这则新闻。

【输入格式】

输入的第一行包含两个整数，第一个整数n，表示学员的数量。学员从1到n编号。第二个整数m,表示有m对人加了微信好友

接下来m行，每行两个整数a, b，用一个空格分隔，表示这两个编号的学员之间加了微信好友。

【输出格式】

输出一个整数，表示最终有多少个学员看到了这则新闻。

【样例输入】

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

【样例输出】

4

【提示】

1<= n <= 1000， 1 <= m <= 10000。

【来源】

在此键入。

这可真是一道无聊的题

常数较小

暴力dfs跑过！

#include<bits/stdc++.h>
#define maxn 1005
using namespace std;
int n,m;
vector<int> v[maxn];
bool vis[maxn];
int ans=0;
void dfs(int p)
{
    if(vis[p])
        return;
    ans++;
    vis[p]=true;
    for(int i=0;i<v[p].size();i++)
        dfs(v[p][i]);    
}
int main()
{
    freopen("friendscircle.in","r",stdin);
    freopen("friendscircle.out","w",stdout); 
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1);
    printf("%d",ans);
    return 0;
}