1 #include<bits/stdc++.h>
2 #define in(a) scanf("%d",&a)
3 using namespace std;
4
5 struct nod
6 {
7 int v,next;
8 }side[
405555];
9
10 int head[
200005],cnt,index,fri[
200005];
11
12 void add(
int u,
int v)
13 {
14 side[cnt].v=
v;
15 side[cnt].next=
head[u];
16 head[u]=cnt++
;
17 fri[u]++
;
18
19 }
20
21 int scc[
200005],dfn[
200005],low[
2000005],ins[
200005],vis[
200005],stac[
200005],tail;
22
23 void tarjan(
int cur)
24 {
25 dfn[cur]=low[cur]=index++
;
26 ins[cur]=
1;
27 vis[cur]=
1;
28 stac[tail++]=
cur;
29 for(
int i=head[cur];i!=-
1;i=
side[i].next)
30 {
31 int c=
side[i].v;
32 if(!
vis[c])
33 {
34 tarjan(c);
35 low[cur]=
min(low[cur],low[c]);
36 }
37 else if(ins[c])
38 low[cur]=
min(low[cur],dfn[c]);
39 }
40 if(dfn[cur]==
low[cur])
41 {
42 cnt++
;
43 int v;
44 do
45 {
46 v=stac[tail-
1];
47 scc[v]=
cnt;
48 ins[v]=
0;
49 tail--
;
50 }
while(v!=
cur);
51 }
52 }
53
54 int main()
55 {
56 int N;
57 in(N);
58 while(N--
)
59 {
60 memset(head,-
1,
sizeof(head));
61 memset(ins,
0,
sizeof(ins));
62 memset(vis,
0,
sizeof(vis));
63 memset(fri,
0,
sizeof(fri));
64 int n,m,k,x,y;
65 in(n);
in(m);
in(k);
66 cnt=
0;
67 for(
int i=
0;i<m;i++
)
68 {
69 in(x);
in(y);
70 add(x,y);add(y,x);
71 }
72 index=
0;tail=
0;cnt=
0;
73 int maxn=
0;
74 for(
int i=
0;i<n;i++
)
75 {
76 if(!
vis[i])
77 tarjan(i);
78 maxn=
max(maxn,fri[i]);
79 }
80 if(maxn+cnt-
1+k>n-
1)
81 printf(
"%d\n",n-
1);
82 else
83 printf(
"%d\n",maxn+cnt-
1+
k);
84
85
86 }
87 return 0;
88 }
View Code
转载于:https://www.cnblogs.com/Taskr212/p/9463327.html
相关资源：JAVA上百实例源码以及开源项目
