QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#135066#6634. Central Subsetsilly_1_2_3#TL 45ms9444kbC++141.2kb2023-08-05 11:02:422023-08-05 11:02:44

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-05 11:02:44]
  • 评测
  • 测评结果:TL
  • 用时:45ms
  • 内存:9444kb
  • [2023-08-05 11:02:42]
  • 提交

answer

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),i##z=(b);i<=i##z;i++)
#define ROF(i,a,b) for(int i=(a),i##z=(b);i>=i##z;i--)
#define REP(i,u) for(int i=hd[u],v;v=to[i],i;i=nxt[i])
#define temT template<typename T>
#define temT12 template<typename T1,typename T2>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
const int N=int(2e5)+10;

temT void clearDS(T &x){ T y; swap(x,y); }

int T,n,m,B; vector<int> edg[N]; int deg[N];
queue<int> leaf,ans; int vis[N],tim;

void dfs(int t,int dis){
	if(dis>B) return ;
//	if(vis[t]==tim) return ;
	vis[t]=tim; deg[t]=0;
//	for(int v:edg[t]) if(vis[v]<tim){
	for(int v:edg[t]){
		if(vis[v]<tim) deg[v]--;
		dfs(v,dis+1);
	}
}

int main(){
	for(cin>>T;T--;){
		cin>>n>>m; B=ceil(sqrt(1.0*n));
		FOR(i,1,n) deg[i]=0,clearDS(edg[i]); clearDS(leaf),clearDS(ans);
		for(int i=1,u,v;i<=m;i++)
			cin>>u>>v,edg[u].push_back(v),edg[v].push_back(u),deg[u]++,deg[v]++;
		FOR(i,1,n) leaf.push(i);
		
		tim++;
		while(leaf.size()){
			int t=leaf.front(); leaf.pop(); 
			if(vis[t]==tim) continue;
			dfs(t,0); ans.push(t);
		}
		
		cout<<ans.size()<<"\n";
		while(ans.size()) (cout<<ans.front()<<" "),ans.pop();
		cout<<"\n";
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 9028kb

input:

2
4 3
1 2
2 3
3 4
6 7
1 2
2 3
3 1
1 4
4 5
5 6
6 4

output:

2
1 4 
1
1 

result:

ok correct (2 test cases)

Test #2:

score: 0
Accepted
time: 45ms
memory: 9444kb

input:

10000
15 14
13 12
5 4
9 8
11 12
15 14
10 9
14 13
2 3
2 1
6 5
10 11
3 4
7 6
8 7
6 5
2 1
2 4
4 6
2 3
3 5
10 9
8 3
9 4
5 6
5 10
3 2
5 4
2 7
1 2
4 3
2 1
2 1
2 1
2 1
9 8
9 8
5 4
1 2
6 5
3 4
3 2
7 8
7 6
2 1
1 2
14 13
3 10
5 6
2 9
11 4
2 3
2 1
8 7
13 6
5 4
5 12
6 7
4 3
7 14
16 15
2 3
2 1
6 10
6 9
6 4
9 11
...

output:

3
1 6 11 
1
1 
2
1 6 
1
1 
1
1 
3
1 5 9 
1
1 
2
1 6 
3
1 7 15 
1
1 
4
1 7 13 19 
2
1 6 
2
1 6 
2
1 11 
1
1 
3
1 6 11 
1
1 
1
1 
2
1 9 
1
1 
2
1 4 
2
1 6 
2
1 6 
2
1 13 
1
1 
3
1 6 11 
1
1 
2
1 6 
1
1 
1
1 
4
1 7 13 19 
3
1 9 11 
2
1 6 
3
1 10 13 
1
1 
2
1 5 
3
1 6 7 
2
1 6 
3
1 9 15 
1
1 
3
1 6 11 
...

result:

ok correct (10000 test cases)

Test #3:

score: -100
Time Limit Exceeded

input:

100
2000 1999
529 528
885 884
1221 1222
375 374
245 244
758 757
711 710
1521 1522
1875 1874
749 750
823 822
1959 1958
1767 1766
155 154
631 632
825 824
1330 1331
457 456
1344 1343
1817 1818
413 414
582 583
1828 1827
1335 1336
654 655
162 161
1668 1667
1966 1967
1472 1471
1185 1184
518 517
1509 1510
...

output:


result: