Codeforces 405E Graph Cutting

Graph Cutting

不会写。。

dfs的过程中把回边丢到它的祖先中去, 回溯的时候两两配对。感觉好神奇啊。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = 1e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-); int n, m;
bool vis[N];
vector<int> G[N];
queue<int> que[N];
vector<pair<int, PII>> ans; void dfs(int u, int fa) {
vis[u] = true;
for(auto& v : G[u]) {
if(!vis[v]) {
dfs(v, u);
} else if(v != fa && vis[v]) {
que[v].push(u);
}
}
while(SZ(que[u]) >= ) {
int x = que[u].front(); que[u].pop();
int y = que[u].front(); que[u].pop();
ans.push_back(mk(x, mk(u, y)));
}
if(SZ(que[u])) {
if(!fa) {
puts("No solution");
exit();
}
int x = que[u].front(); que[u].pop();
ans.push_back(mk(x, mk(u, fa)));
} else {
que[fa].push(u);
}
} int main() {
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
if(m & ) puts("No solution");
else {
dfs(, );
for(auto& t : ans)
printf("%d %d %d\n", t.fi, t.se.fi, t.se.se);
}
return ;
} /*
*/
上一篇:ORA-12537: TNS:connection closed错误处理过程


下一篇:jquery之DataTables的使用