求助
查看原帖
求助
924622
wr3244416265楼主2023/11/5 21:46

90求调,数据在下面

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
const int N=1e5+5;
int n,qp;
int siz[N],son[N],ans,fa[N];
struct node{
	int ne,to;
}e[N];
int h[N],cnt,vis[N];
void add(int u,int v){
	e[++cnt].ne=h[u];
	e[cnt].to=v;
	h[u]=cnt;
	e[++cnt].ne=h[v];
	e[cnt].to=u;
	h[v]=cnt;
}
void dfs(int u,int fat){
	siz[u]=1;fa[u]=fat;
	for(int i=h[u];i;i=e[i].ne){
		int v=e[i].to;
		if(v==fat) continue;
		dfs(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]]) son[u]=v;
	}
}
queue<int> q,q1;
signed main(){
	scanf("%lld%lld",&n,&qp);
	for(int i=1;i<=qp;i++){
		int x,y;
		scanf("%lld%lld",&x,&y);
		add(x,y);
	}
	dfs(1,0);
	q.push(1);
	while(!q.empty()){
		int maxn=0;
		while(!q.empty()){
			int x=q.front();
			q.pop();
			if(vis[x]) continue;
			for(int i=h[x];i;i=e[i].ne){
				int v=e[i].to;
				if(v==fa[x]) continue;
				if(siz[v]>siz[maxn]) maxn=v;
			}
			q1.push(x);
		}
		vis[maxn]=1;
		while(!q1.empty()){
			int x=q1.front();
			q1.pop();
			if(vis[x]) continue;
			for(int i=h[x];i;i=e[i].ne){
				int v=e[i].to;
				if(v==fa[x]) continue;
				if(vis[v]) continue;
				q.push(v);
			}
		}
	}
	ans+=siz[1];
	for(int i=1;i<=n;++i) if(vis[i]) ans-=siz[i];
	printf("%lld\n",ans);
	return 0;
}
/*
100 99
2 1
3 2
4 3
5 3
6 3
7 2
8 7
9 7
10 9
11 7
12 2
13 12
14 12
15 12
16 2
17 16
18 17
19 17
20 16
21 2
22 21
23 21
24 21
25 1
26 25
27 26
28 25
29 28
30 25
31 30
32 31
33 31
34 31
35 30
36 35
37 35
38 37
39 37
40 1
41 40
42 41
43 41
44 41
45 41
46 40
47 46
48 40
49 40
50 49
51 40
52 51
53 51
54 40
55 54
56 54
57 1
58 57
59 58
60 58
61 58
62 57
63 62
64 62
65 62
66 57
67 66
68 66
69 66
70 66
71 57
72 71
73 71
74 71
75 74
76 57
77 76
78 76
79 76
80 76
81 1
82 81
83 82
84 83
85 82
86 85
87 81
88 87
89 88
90 88
91 87
92 87
93 92
94 92
95 94
96 92
97 96
98 96
99 92
100 99

*/
/*55*/
2023/11/5 21:46
加载中...