QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#777938 | #8757. 图 | hotdogseller | TL | 0ms | 0kb | C++14 | 2.4kb | 2024-11-24 11:27:34 | 2024-11-24 11:27:35 |
answer
#include<bits/stdc++.h>
#define INF 1e18
#define int long long
#define maxn 100005
using namespace std;
inline int read(){
int lre=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-'){
f=-1;
}
c=getchar();
}
while(c>='0'&&c<='9'){
lre=(lre<<3)+(lre<<1)+(c-'0');
c=getchar();
}
return lre*f;
}
struct edge{
int to;
int val;
int next;
}e[4*maxn];
int e_cnt=1,head[maxn];
int add(int u,int v,int w){
e[e_cnt].to=v;
e[e_cnt].val=w;
e[e_cnt].next=head[u];
head[u]=e_cnt++;
}
int n,m;
//vector<vector<int> > root;
int cnt=0;
map<int,map<int,int> > root;
bool okay=false;
bool visited[maxn];
vector<int> ans;//遍历路径
int f_f(int x,int y){
if(root[y][x]==0)root[y][x]=x;
if(root[y][x]!=x){
root[y][x]=f_f(root[y][x],y);
}
return root[y][x];
}
void merge(int u,int v,int y){
if(root[y][u]==0)root[y][u]=u;
if(root[y][v]==0)root[y][v]=v;
root[y][f_f(u,y)]=f_f(v,y);
}
void dfs(int x,int color,int goal){
// cout<<"x="<<x<<endl;
visited[x]=true;
ans.push_back(x);
if(x==goal){
okay=true;
printf("%lld ",ans.size());
for(int i=0;i<ans.size();++i){
printf("%lld ",ans[i]);
}
putchar('\n');
}else{
for(int i=head[x];i;i=e[i].next){
int v=e[i].to,w=e[i].val;
if(w!=color)continue;
if(visited[v])continue;
dfs(v,color,goal);
if(okay)break;
}
}
visited[x]=false;
ans.pop_back();
}
void solve(){
e_cnt=1;root.clear();cnt=0;
n=read();m=read();
for(int i=0;i<=n;i++){
head[i]=0;visited[i]=false;
}
for(int i=1;i<=m;i++){
int u=read(),v=read();
if(cnt==0){
cnt++;
merge(u,v,cnt);
add(u,v,cnt);add(v,u,cnt);
}else if(f_f(u,cnt)==f_f(v,cnt)){
cnt++;
merge(u,v,cnt);
add(u,v,cnt);add(v,u,cnt);
}else{
int l=1,r=cnt,mid,ind;
while(l<=r){
mid=l+r>>1;
if(f_f(u,mid)==f_f(v,mid)){
l=mid+1;
}else{
ind=mid;
r=mid-1;
}
}
// cout<<"merge in "<<ind<<endl;
merge(u,v,ind);
add(u,v,ind);add(v,u,ind);
}
}
int x,y;
for(int i=1;i<=n;i++){
x=f_f(i,cnt);
if(x!=i){
y=x;x=i;
break;
}
}
swap(x,y);
printf("%lld %lld\n",x,y);
int k=(n+m-2)/(n-1);
if(cnt<k)printf("-1\n");
else{
for(int i=1;i<=k;i++){
okay=false;
dfs(x,i,y);
}
}
}
signed main(){
int t=read();
while(t--){
solve();
}
return 0;
}
/*
1
100000 1
55772 64101
*/
详细
Test #1:
score: 0
Time Limit Exceeded
input:
10000 2 20 1 2 1 2 2 1 1 2 1 2 2 1 1 2 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 1 2 2 1 2 20 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 2 20 1 2 2 1 1 2 1 2 2 1 2 1 1 2 1 2 2 1 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 1 2 2 1 2 1 2 20 1 2 2 1 2 1 1 2 1 2 1 2 2 1 1 2 2 ...