最近做了下题，作业题目有一道很有意思的题目
[CF 711D](https://codeforces.com/problemset/problem/711/D)
这道题问的是给出一个必存在至少一个环的图里面，每次操作可以选出来一些边，每条有向边可以被反转，然后问最后能让这个图无环的方案有多少种
其实熟悉基环树的都一眼能看出来这就是基环树，因为n == m代表图中存在一个大环，我们随意反转树上的边是不影响的，所以我们可以选出来0- n - 1条边(树的大小)
这个很显然，有每个子树对答案的贡献是pow(2, 大小 + 1) - 2
然后处理完剩下的自然就是环了，所以把 |图大小 - 子树大小| 即为环，基环上任意一点反转，则环消失变为dag，但不能同时转向（又成环了），所以总数有pow(2, n - tot)种
乘起来取模就好了，妙哇！
#include <bits/stdc++.h>
using namespace std;
constexpr int limit = (4000000 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ff(a) printf("%d\n",a );
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll sign = 1, x = 0;
char s = getchar();
while (s > '9' || s < '0') {
if (s == '-')sign = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * sign;
#undef getchar
}//快读
void print(ll x) {
if (x / 10) print(x / 10);
*O++ = x % 10 + '0';
}
void write(ll x, char c = 't') {
if (x < 0)putchar('-'), x = -x;
print(x);
if (!isalpha(c))*O++ = c;
fwrite(obuf, O - obuf, 1, stdout);
O = obuf;
}
constexpr ll mod = 1e9 + 7;
ll quickPow(ll base, ll expo){
ll ans = 1;
while (expo){
if(expo & 1)(ans *= base) %= mod;
expo >>= 1;
base = base * base;
base %= mod;
}
return ans % mod;
}
ll C(ll n, ll m){
if(n < m)return 0;
ll x = 1, y = 1;
if(m > n - m)m = n - m;
rep(i ,0 , m - 1){
x = x * (n - i) % mod;
y = y * (i + 1) % mod;
}
return x * quickPow(y, mod - 2) % mod;
}
ll lucas(ll n, ll m){
return !m || n == m ? 1 : C(n % mod, m % mod) * lucas(n / mod, m / mod) % mod;
}
int n, m, k;
int a[limit];
ll fact[limit];
void calc(){
fact[0] = 1;
rep(i, 1, limit - 1){
fact[i] = fact[i - 1] * i % mod;
}
}
int top[limit];
ll ans = 1;
int depth[limit];
ll tot;
void dfs(int u, int dep, int tp){
depth[u] = dep;
top[u] = tp;
if(!top[a[u]]){
dfs(a[u], dep + 1, tp);
}else if(top[u] == top[a[u]]){
(ans *= quickPow(2, dep - depth[a[u]] + 1) - 2) %= mod;
tot += dep - depth[a[u]] + 1;
}
}
void solve(){
cin>>n;
rep(i,1,n){
cin>>a[i];
}
rep(i, 1, n){
if(!top[i]){
dfs(i, 1, i);
}
}
cout<<(((ans *= quickPow(2, n - tot))) %= mod)<<endl;
};
int32_t main() {
#ifdef LOCAL
FOPEN;
// FOUT;
#endif
FASTIO
// int kase;
// calc();
// cin>>kase;
// while (kase--)
solve();
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
return 0;
}
AC Code
然后说到了基环树，好像没怎么涉及到这一块，所以做这种题就是直接两眼一抹黑，所以还是得看
然后看到了基环树定义，其实并不难理解，就是树根是一个环，然后其他地方和树的性质一样
记得刚开始学习算法竞赛的时候，看到过一篇NOI游记，说基环树要断边
那么来看看P5022旅行吧
所以这道题是问从某点出发，到能够到达的最大的地方，要求字典序最大的，题中很贴心地描述了回溯的过程
首先有向图很好搞，直接把边排序贪心就好了，但需要特殊处理的是基环树
题中某些情况(n == m)可以构成基环树，因为是基环树，我们需要从环上某一点切入，某一点改出，但我们不知道是从哪一点进行改出，所以我们枚举边，进行一个断边的操作，之后不断暴力比较字典序就好了
下周就学基环树好了
很奇妙
#include <bits/stdc++.h>
using namespace std;
constexpr int limit = (50000 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ff(a) printf("%d\n",a );
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll sign = 1, x = 0;
char s = getchar();
while (s > '9' || s < '0') {
if (s == '-')sign = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * sign;
#undef getchar
}//快读
void print(ll x) {
if (x / 10) print(x / 10);
*O++ = x % 10 + '0';
}
void write(ll x, char c = 't') {
if (x < 0)putchar('-'), x = -x;
print(x);
if (!isalpha(c))*O++ = c;
fwrite(obuf, O - obuf, 1, stdout);
O = obuf;
}
constexpr ll mod = 1e9 + 7;
ll quickPow(ll base, ll expo){
ll ans = 1;
while (expo){
if(expo & 1)(ans *= base) %= mod;
expo >>= 1;
base = base * base;
base %= mod;
}
return ans % mod;
}
ll C(ll n, ll m){
if(n < m)return 0;
ll x = 1, y = 1;
if(m > n - m)m = n - m;
rep(i ,0 , m - 1){
x = x * (n - i) % mod;
y = y * (i + 1) % mod;
}
return x * quickPow(y, mod - 2) % mod;
}
ll lucas(ll n, ll m){
return !m || n == m ? 1 : C(n % mod, m % mod) * lucas(n / mod, m / mod) % mod;
}
int n, m, k;
int a[limit<<1];
ll fact[limit];
void calc(){
fact[0] = 1;
rep(i, 1, limit - 1){
fact[i] = fact[i - 1] * i % mod;
}
}
vector<int>g[limit], ans = {0}, temp = {0};
int vis[limit];
void add(int x, int y){
g[x].push_back(y);
g[y].push_back(x);
}
void dfs(int u, int pre, int delu, int delv){
if(vis[u])return;
vis[u] = 1;
temp.push_back(u);
for(auto v : g[u]){
if(v == pre or min(u, v) == min(delu, delv) and max(u, v) == max(delu, delv))continue;
dfs(v, u, delu, delv);
}
}
void solve(){
cin>>n>>m;
rep(i,1,m){
cin>>a[i]>>a[i + m + 1];
add(a[i], a[i + m + 1]);
}
rep(i,1,n){
ranges::sort(g[i]);
}
if(n == m){
rep(i,1,m){
int u = a[i], v = a[i + m + 1];
temp.clear();
temp.push_back(0);
memset(vis, 0, sizeof vis);
dfs(1, -1, u, v);
if(temp.size() < n + 1){
continue;
}
if(ans.size() == 1 or temp < ans){
ans.swap(temp);
}
}
}else{
dfs(1, -1, -1, -1);
ans.swap(temp);
}
for(auto && it : ans | views::drop(1)){
cout<<it<<' ';
}
};
int32_t main() {
#ifdef LOCAL
FOPEN;
// FOUT;
#endif
FASTIO
// int kase;
// calc();
// cin>>kase;
// while (kase--)
solve();
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
return 0;
}
AC Code
标签：专题,int,ll,基环树,mod,rep,define From： https://www.cnblogs.com/tiany7/p/16882618.html