太仓市住房和城乡建设局规网站,自学设计软件的免费网站,万网怎样安装wordpress,怎么做微信推广和宣传题意#xff1a;
n个学生要组成一个小组参加会议#xff08;可以不参加#xff09;#xff0c; 1.对于每两个朋友#xff08;x #xff0c;y)#xff0c;如果他们俩都参加会议#xff0c;该小组的友好价值将会增加 1#xff1b;如果其中只有一位参加会议#xff0c;…题意
n个学生要组成一个小组参加会议可以不参加 1.对于每两个朋友x y)如果他们俩都参加会议该小组的友好价值将会增加 1如果其中只有一位参加会议则该组的友好价值将降低 1。 3.如果n个学生参加会议对团队的友好价值将降低n.
题目
Professor Alex will organize students to attend an academic conference.
Alex has n excellent students, and he decides to select some of them (possibly none) to attend the conference. They form a group. Some pairs of them are friends.
The friendly value of the group is initially 0. For each couple of friends (x,y), if both of them attend the conference, the friendly value of the group will increase 1, and if only one of them attends the conference, the friendly value of the group will decrease 1. If k students attend the conference, the friendly value of the group will decrease k.
Alex wants to make the group more friendly. Please output the maximum friendly value of the group.
Input
The first line of the input gives the number of test cases, T (1≤T≤104). T test cases follow.
For each test case, the first line contains two integers n (1≤n≤3×105) and m (1≤m≤106), where n is the number of students and m is the number of couples of friends.
Each of the following m lines contains two integers xi,yi (1≤xi,yi≤n,xi≠yi), representing student xi and student yi are friends. It guaranteed that unordered pairs (xi,yi) are distinct.
The sum of n in all test cases doesn’t exceed 106, and the sum of m in all test cases doesn’t exceed 2×106.
Output
For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1), and y is the maximum friendly value of the group.
Example
Input
2 4 5 1 2 1 3 1 4 2 3 3 4 2 1 1 2
Output
Case #1: 1 Case #2: 0
分析
1.由题意友好价值组群里的边数-点数 2.那么怎么求最大友好价值由于对于每两个朋友x y)如果他们俩都参加会议该小组的友好价值将会增加 1如果其中只有一位参加会议则该组的友好价值将降低 1所以我们用并查集直接找根节点遍历到最后这时就变成了一个个的组群我们只要判断这些组群是否参加会议即可当组群里的边数-点数0时不让其参加反之参加即可求得。
AC代码
#includebits/stdc.h
using namespace std;
const int M3e510;
int t,n,m,k,ans;
int f[M],a[M],b[M];
int getf(int x){if(f[x]x) return x;return f[x]getf(f[x]);
}
int main(){cint;k0;while(t--){cinnm;for(int i1;in;i){f[i]i;a[i]0;//记录边起始边个数为零。b[i]1;//记录点原始本身就为一个点。}for(int i1;im;i){int t1,t2;scanf(%d%d,t1,t2);int ugetf(t1);int vgetf(t2);if(uv) a[u];else {f[v]u;a[u]a[v]1;//因为最终怕判断的根节点判组群所以记录边和点只需要在根节点上即可。b[u]b[v];}}ans0;for(int i1;in;i){if(if[i]a[i]-b[i]0)ansa[i]-b[i];}printf(Case #%d: %d\n,k,ans);}return 0;
}
