QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#127104 | #6634. Central Subset | doyo# | TL | 2ms | 11632kb | C++14 | 1.4kb | 2023-07-19 12:59:26 | 2023-07-19 12:59:28 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+5;
struct Edge
{
int next;int to;
}edge[maxn];
int dep[maxn],n,sqn,head[maxn],cnt,m;
bool sel[maxn],vis[maxn];
void addedge(int from,int to)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
head[from]=cnt;
}
int dfs(int u,int fat)
{
//返回值为所能访问到的节点的最大深度
vis[u]=true;
dep[u]=dep[fat]+1;
int maxdep=dep[u];
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fat||vis[v]) continue;
int tmp=dfs(v,u);
maxdep=max(maxdep,tmp);
}
//printf("dep[%d]=%d,maxdep=%d\n",u,dep[u],maxdep);
if(maxdep-dep[u]==sqn)
{
sel[u]=true;
return 0;
}
else return maxdep;
}
vector<int> ans;
void work()
{
cin>>n>>m;
if(n/sqrt(n)==sqrt(n)) sqn=sqrt(n);
else sqn=(int)sqrt(n)+1;
//printf("sqn=%d\n",sqn);
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
addedge(x,y);
addedge(y,x);
}
dep[0]=0;
dfs(1,0);
for(int i=1;i<=n;i++)
if(sel[i]) ans.push_back(i),sel[i]=false;
cout<<ans.size()<<endl;
for(auto item:ans)
cout<<item<<' ';
for(int i=1;i<=n;i++) vis[i]=false;
}
int main()
{
cin.tie(0);
cin.sync_with_stdio(0);
int t=1;
cin>>t;
while(t--)
work();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11632kb
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:
1 2 2 2 1
result:
ok correct (2 test cases)
Test #2:
score: -100
Time Limit Exceeded
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 4 1 6 11 3 6 1 6 11 3 2 8 7 1 6 11 3 2 8 1 7 1 6 11 3 2 8 1 9 1 6 11 3 2 8 1 5 8 10 1 6 11 3 2 8 1 5 8 1 13 1 6 11 3 2 8 1 5 8 1 4 7 12 15 1 6 11 3 2 8 1 5 8 1 4 7 12 3 6 17 1 6 11 3 2 8 1 5 8 1 4 7 12 3 6 9 12 21 1 6 11 3 2 8 1 5 8 1 4 7 12 3 6 9 12 1 6 11 16 22 1 6 11 3 2 8 1 5 8 1 4 7 12...