QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#135066 | #6634. Central Subset | silly_1_2_3# | TL | 45ms | 9444kb | C++14 | 1.2kb | 2023-08-05 11:02:42 | 2023-08-05 11:02:44 |
Judging History
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 ...