UVA 10608 Friends

题目大意:共有n个人,m对人为已知的朋友关系,而且这种关系具有传递性,也就是A与B,B与C是朋友,可以确定A与C是朋友,求一个人数最多的朋友团体。

bfs就可以了,遇到未访问的结点,加入队列并且朋人数增加,bfs一开始只访问未访问的结点,并作为一个团体的开始。、

代码:

 #include <iostream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#define esp 1e-6
#define pb push_back
#define in freopen("in.txt", "r", stdin);
#define out freopen("out.txt", "w", stdout);
#define print(a) printf("%d\n",(a));
#define bug puts("********))))))");
#define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++)
#define inf LLONG_MAX
#define INF 0x0f0f0f0f0f0f
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef vector<int>:: iterator IT;
#define N 30010
#define M 501000
VI g[N], ss;
int vis[N], ans, temp;
void init(void)
{
ans = ;
memset(vis, , sizeof(vis));
}
void bfs(int u)
{
temp = ;
vis[u] = ;
queue<int> q;
q.push(u);
while(!q.empty())
{
int i;
i = q.front();
q.pop();
Rep(k, g[i])
{
if(!vis[*k])
vis[*k] = ,temp++, q.push(*k);
} }
}
int main(void)
{
int T;
for(int t = scanf("%d", &T); t <= T ; t++)
{
for(int i = ; i < N; i++)
g[i].clear();
ss.clear();
init();
int n, m;
scanf("%d%d", &n, &m);
while(m--)
{
int u, v;
scanf("%d%d", &u, &v);
g[u].pb(v);
g[v].pb(u);
ss.pb(u),ss.pb(v);
}
Rep(i, ss)
{
temp = ;
if(!vis[*i])
bfs(*i);
ans = max(temp, ans);
}
printf("%d\n", ans);
}
return ;
}
上一篇:转 JavaScript中判断对象类型的种种方法


下一篇:Happy 2006 POJ - 2773 容斥原理+二分