SDUT完美网络

用优先队列做，凡是小于2的度进入队列。第一组数据有点问题。 #include<stdio.h> #include<string.h> #include<queue> #include<algorithm> using namespace std; int net[10005]; int main() { int t,i,n,m,x,y,a,b,num,k; priority_queue<int,vector<int>,greater<int> > q; scanf("%d",&t); while(t--) { a=b=num=k=0; memset(net,0,sizeof(net)); scanf("%d %d",&n,&m); for(i=1;i<=m;i++) { scanf("%d %d",&x,&y); net[x]++; net[y]++; } sort(net+1,net+1+n); for(i=1;i<=n;i++) { if(net[i]<=1) q.push(net[i]); } while(q.size()>=2) { a=q.top(); q.pop(); b=q.top(); q.pop(); a++; b++; num++; if(a<2) q.push(a); if(b<2) q.push(b); } if(!q.empty()) num++; printf("%d\n",num); } }