AcWing 1184欧拉回路（打板子踩坑记）
标签：get als ret ons amp 情况 vector nbsp wing
题目大意：
先给个T，T=1就代表数据是无向图，T=2就代表数据是有向图
然后给n, m，表示有n个结点，m条边。
之后判断有没有欧拉回路，没有就输出"NO"，有就输出"YES"并输出一条路径
注意：有重边跟自环！
原题链接：https://www.acwing.com/problem/content/1186/
嗯？欧拉板子？然后我一波操作猛如虎，一点提交TLE。
Why？
一波分析下来，发现是这个自环搞的鬼，我写的是双vector嵌套存图，导致碰到自环时会出现重复遍历边的情况，时间复杂度就变成了O(V+E2)，哎，还是太年轻了。
嗯，所以就给每个点加个边的遍历起点，然后在dfs里看看进入递归前后的遍历起点有没有变化，有变化就说明是进入了重边，那么这个点就是在那个dfs里遍历过了，break就行，没有变化就照常遍历。
代码：
#include
#include
#includeusing namespace std;
const int Maxn = 2e5 + 10;
bool visit[Maxn*2 + 100];
int fa[Maxn];
int indegree[Maxn];
int outdegree[Maxn];
int ans[Maxn];
int cur;
int Next[Maxn];
struct Edge{
int v;
int id;
Edge(int v, int id) : v(v), id(id) {}
};
vector > G(Maxn);
int T;
int find(int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
bool issame(int a, int b)
{
return find(a) == find(b);
}
void unite(int a, int b)
{
if(!issame(a, b)){
fa[find(a)] = find(b);
}
}
bool isOK(int n)
{
int pre = -1;
if(T == 1){
for(int i=1; i){
if(pre != find(i) && G[i].size() != 0){
if(pre == -1) pre = find(i);
else return false;
}
if(indegree[i] & 1) return false;
}
}
else if(T == 2){
for(int i=1; i){
if(pre != find(i) && G[i].size() != 0){
if(pre == -1) pre = find(i);
else return false;
}
if(indegree[i] != outdegree[i]) return false;
}
}
return true;
}
void dfs(int x, int pre)
{
for(int i=Next[x]; i){
int v = G[x][i].v;
int id = G[x][i].id;
Next[x] = i+1;
int pre = Next[x];
if(visit[abs(id)]) continue;
visit[abs(id)] = true;
dfs(v, id);
if(pre != Next[x]) break;
}
if(pre != 0) ans[cur++] = pre;
}
int main()
{
cin>>T;
int n, m;
cin>>n>>m;
for(int i=1; i)
fa[i] = i;
int start = 1;
for(int i=1; i){
int u, v;
cin>>u>>v;
start = u;
if(T == 1){
G[u].push_back(Edge(v, i));
G[v].push_back(Edge(u, -i));
indegree[u]++;
indegree[v]++;
outdegree[u]++;
outdegree[v]++;
}
else{
G[u].push_back(Edge(v, i));
outdegree[u]++;
indegree[v]++;
}
unite(u, v);
}
if(!isOK(n)) cout"NO";
else{
cout"YES"endl;
dfs(start, 0);
for(int i=cur-1; i>=0 ;i--)
cout" ";
}
return 0;
}
AcWing 1184欧拉回路（打板子踩坑记）
标签：get als ret ons amp 情况 vector nbsp wing
原文地址：https://www.cnblogs.com/wulichenai/p/12632219.html
评论