#include<bits/stdc++.h>
//#define int long long
#define rep(i, l, r) for(register int i = l;i <= r; ++ i)
using namespace std;
inline int read()
{
register char cc = getchar(); register int cn(0), flus(1);
while(cc > '9' || cc < '0') {if(cc == '-') flus = -flus; cc = getchar();}
while(cc >= '0' && cc <= '9') {cn = cn * 10 + cc - 48; cc = getchar();}
return cn * flus;
}
const int N = 1000010;
struct edge
{
int to, next;
bool del;
} e[N << 1];
int tot, head[N];
int n, m;
bool vis[N];
bool flag;
bool cir[N];
int point_in(1);
bool del = 0;
inline void add(int u, int v)
{
e[++tot].next = head[u];
head[u] = tot;
e[tot].to = v;
e[++tot].next = head[v];
head[v] = tot;
e[tot].to = u;
return ;
}
//priority_queue<int> que;
void dfs(int u, int last)
{
printf("%d ",u);
priority_queue<int, deque<int>, greater<int> > que;
for(register int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
if(v == last || e[i].del) continue;
//dfs(v, u);
que.push(v);
}
while(!que.empty())
{
int v = que.top();
que.pop();
dfs(v, u);
}
}
void dfs1(int u, int last)
{
vis[u] = 1;
for(register int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
if(v == last || e[i].del) continue;
if(vis[v])
{
flag = 1;
cir[v] = 1;
cir[u] = 1;
return ;
}
dfs1(v, u);
if(cir[v] && flag)
{
if(cir[u]) flag = 0;
cir[u] = 1;
return ;
}
}
}
void dfs2(int u, int last)
{
// printf("dfs2 %d \n",u);
vis[u] = 1;
for(register int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
// printf("v = %d \n",v);
if(v == last) continue;
if(cir[v])
{
point_in = v;
return ;
}
}
}
int back(int u, int last)
{
// printf("back %d %d \n",u,last);
// priority_queue<int, deque<int>, greater<int> > q;
int _min(1e9);
int nxt;
for(register int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
// printf("v = %d \n",v);
if(v == last) continue;
if(!vis[v]) _min = min(_min, v);
if(cir[v]) nxt = v;
}
// printf("_min = %d \n",_min);
if(_min != 1e9)
{
return _min;
}
return back(nxt, u);
}
void dfs4(int u, int last)
{
printf("");
// printf("dfs4 %d %d \n",u,last);
vis[u] = 1;
priority_queue<int, deque<int>, greater<int> > q;
for(register int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
if(v == last) continue;
q.push(v);
}
bool first(0);
while(!q.empty())
{
if(del) return ;
int v = q.top();
q.pop();
if(cir[v] && q.empty())
{
if(back(u, v) < v)
{
// printf("back(%d,%d) = %d \n",u,v,back(u, v));
for(register int i = head[u]; i; i = e[i].next)
{
int v1 = e[i].to;
if(v1 == v)
{
e[i].del = 1;
if(e[i + 1].to == u) e[i + 1].del = 1;
else if(e[i - 1].to == u) e[i - 1].del = 1;
}
}
del = 1;
return ;
}
}
dfs4(v, u);
}
return ;
}
signed main()
{
// printf("fuck \n");
// freopen("in.txt","r",stdin);
n = read(), m = read();
rep(i, 1, m)
{
int u, v;
u = read(), v = read();
add(u, v);
}
if(n == m + 1)
{
dfs(1, 0);
return 0;
}
dfs1(1, 0);
memset(vis, 0, sizeof(vis));
if(!cir[1]) dfs2(1, 0);
// printf("point_in = %d \n",point_in);
dfs4(point_in, 0);
rep(i, 1, n)
{
// printf("cir[%d] = %d \n",i,cir[i]);
}
dfs(1, 0);
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 36.62 us | 52 KB | Accepted | Score: 5 | 显示更多 |
Testcase #2 | 126.5 us | 1 MB + 4 KB | Accepted | Score: 5 | 显示更多 |
Testcase #3 | 68.12 us | 88 KB | Accepted | Score: 5 | 显示更多 |
Testcase #4 | 60.67 us | 96 KB | Accepted | Score: 5 | 显示更多 |
Testcase #5 | 1.31 ms | 2 MB + 400 KB | Accepted | Score: 5 | 显示更多 |
Testcase #6 | 1.29 ms | 2 MB + 172 KB | Accepted | Score: 5 | 显示更多 |
Testcase #7 | 31.33 ms | 41 MB + 276 KB | Accepted | Score: 5 | 显示更多 |
Testcase #8 | 31.833 ms | 27 MB + 516 KB | Accepted | Score: 5 | 显示更多 |
Testcase #9 | 206.544 ms | 209 MB + 432 KB | Accepted | Score: 5 | 显示更多 |
Testcase #10 | 210.735 ms | 245 MB + 356 KB | Accepted | Score: 5 | 显示更多 |
Testcase #11 | 205.702 ms | 141 MB + 56 KB | Accepted | Score: 5 | 显示更多 |
Testcase #12 | 209.091 ms | 179 MB + 864 KB | Accepted | Score: 5 | 显示更多 |
Testcase #13 | 1.495 ms | 3 MB + 484 KB | Accepted | Score: 5 | 显示更多 |
Testcase #14 | 1.532 ms | 4 MB + 184 KB | Accepted | Score: 5 | 显示更多 |
Testcase #15 | 35.045 ms | 50 MB + 136 KB | Accepted | Score: 5 | 显示更多 |
Testcase #16 | 36.039 ms | 58 MB + 28 KB | Accepted | Score: 5 | 显示更多 |
Testcase #17 | 272.777 ms | 407 MB + 156 KB | Accepted | Score: 5 | 显示更多 |
Testcase #18 | 273.354 ms | 407 MB + 132 KB | Accepted | Score: 5 | 显示更多 |
Testcase #19 | 249.519 ms | 220 MB + 712 KB | Accepted | Score: 5 | 显示更多 |
Testcase #20 | 265.005 ms | 324 MB + 672 KB | Accepted | Score: 5 | 显示更多 |