贪心只有 90pts,看了看题解说是错解,但似乎都没有讲明白。所以来求一组 hack 数据或是讲讲错在了哪里!
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int MAX = 305;
int n,p,ans;
vector <int> v[MAX];
bool vis[MAX];
void work ();
int search (int x);
void out (int x);
int main ()
{
//freopen ("infectious.in","r",stdin);
//freopen ("infectious.out","w",stdout);
scanf ("%d%d",&n,&p);
for (int i = 1;i <= p;++i)
{
int x,y;scanf ("%d%d",&x,&y);
if (x > y) swap (x,y);
v[x].push_back (y);
}
work ();
for (int i = 1;i <= n;++i)
if (!vis[i]) ++ans;
printf ("%d\n",ans);
return 0;
}
void work ()
{
queue <int> q,qq;
qq.push (1);
while (!qq.empty ())
{
while (!qq.empty ()) q.push (qq.front ()),qq.pop ();
vector <int> p;
int sum = 0,k;
while (!q.empty ())
{
int x = q.front ();
q.pop ();
for (int i = 0;i < v[x].size ();++i)
{
int w = search (v[x][i]);
if (w > sum) sum = w,k = v[x][i];
p.push_back (v[x][i]);
}
}
out (k);
for (int i = 0;i < p.size ();++i)
{
if (p[i] == k) continue;
qq.push (p[i]);
}
}
}
int search (int x)
{
int s = 1;
if (v[x].size () == 0) return 1;
for (int i = 0;i < v[x].size ();++i)
s += search (v[x][i]);
return s;
}
void out (int x)
{
vis[x] = 1;
if (v[x].size () == 0) return ;
for (int i = 0;i < v[x].size ();++i) out (v[x][i]);
}