题解 CF962F 【Simple Cycles Edges】

· · 题解

一个奇怪的做法，貌似没有看见相同做法的题解。

首先对于不同的连通块，我们分别处理即可。
发现如果一条边符合条件，当且仅当它所在的点双恰为一个简单环。
于是，我们可以把题意转化为：求所有点数等于边数的点双连通分量。
因为一条边只会在一个点双中出现，于是我们考虑在每条边上新增一个点。
即把这样一张图：

变成这样：

此时，如果我们把原来的 n 个点权值设为 1，新增点的权值设为 -1，相当于要求有多少个点双的点权和为 0。
这是在 Tarjan 过程中可以方便地统计的。
同时，因为每条边只会属于一个点双，所以每个新增点也只会被一个点双包含，记录下来每个新增点对应的点双编号即可。

此时还有一个问题：对于一条不存在于任意一个简单环中的边，我们这样处理会导致误判。
有一个比较笨的解决方法，在新增点之前跑一下原图的 Tarjan，则所有只有两个点的点双就对应一条这样的边，记录下来这些边后新建点时忽略这些边即可。
于是总时间复杂度为 O(n+m)。

代码如下： 

#include <bits/stdc++.h>
using namespace std;
#define ch getchar
template<typename T> void read(T &x){
    x = 0; int f(1); char c = ch();
    for(;!isdigit(c);c = ch()) if(c == '-') f = -1;
    for(;isdigit(c);c = ch()) x = x*10+c-'0';
    x *= f;
}
template<typename T,typename... Args>
inline void read(T &x,Args&... args){
    read(x); read(args...);
}
#define pb emplace_back
const int maxn = 100005;
int n,m,ANS[maxn],cnt;
int hd[maxn],tt = 1; // 注意前向星的开始下标。
struct edge{int ed,nxt;}e[2*maxn];
int dfn[2*maxn],low[2*maxn];
int sta[2*maxn],top,tot;
int val[2*maxn],V[2*maxn];
int eu[maxn],ev[maxn];
vector<int> Frm[2*maxn];
vector<int> G[2*maxn];
void star(int u,int v){
    e[++tt] = (edge){v,hd[u]}; hd[u] = tt;
    e[++tt] = (edge){u,hd[v]}; hd[v] = tt;  
}
void Tarjan(int x){
    dfn[x] = low[x] = ++tot;
    sta[++top] = x;
    for(auto y:G[x]){
        if(!dfn[y]){
            Tarjan(y);
            low[x] = min(low[x],low[y]);
            if(low[y] == dfn[x]){
                ++cnt;
                while(sta[top+1] != y){
                V[cnt] += val[sta[top]];
                    if(val[sta[top]] == -1)
                        Frm[cnt].pb(sta[top]);
                    --top;
                }
                V[cnt] += val[x];
                if(val[x] == -1)    Frm[cnt].pb(x);
                // 统计点权和，并记录每个点双中的新增点。
            }
        }
        else    low[x] = min(low[x],dfn[y]);
    }
}
void tarjan(int x){
    dfn[x] = low[x] = ++tot;
    sta[++top] = x;
    for(int i = hd[x];i;i = e[i].nxt){
        int y = e[i].ed;
        if(!dfn[y]){
            tarjan(y);
            low[x] = min(low[x],low[y]);
            if(low[y] == dfn[x]){
                cnt = 0;
                while(sta[top+1] != y)
                    ++cnt,--top;
                ++cnt;
                if(cnt == 2)    ANS[i/2] = 1;
                // 对于所有大小为 2 的点双，给边打上标记。
            }
        }
        else    low[x] = min(low[x],dfn[y]);
    }
}
int main(){
    read(n,m);
    for(int i(1);i <= m;++i){
        read(eu[i],ev[i]);
        star(eu[i],ev[i]);
    }
    for(int i(1);i <= n;++i)
        if(!dfn[i]) tarjan(i),--top;
//第一次 tarjan，求出不存在于任意一个简单环中的边，并打上标记。
    memset(dfn,0,sizeof dfn);
    tot = top = cnt = 0;
    for(int i(1);i <= n;++i)    val[i] = 1;
    for(int i(1);i <= m;++i){
        if(ANS[i] == 1){ANS[i] = 0;continue;}
        G[eu[i]].pb(n+i); G[ev[i]].pb(n+i);
        G[n+i].pb(eu[i]); G[n+i].pb(ev[i]); val[n+i] = -1;
    }
//新建边上的点。
    n += m;
    for(int i(1);i <= n;++i)
        if(!dfn[i]) Tarjan(i),--top;
//第二次 tarjan，求出所有新图点双的权值和。
    for(int i(1);i <= cnt;++i)
        if(V[i] == 0)
        for(int j(0);j < Frm[i].size();++j)
            ANS[Frm[i][j]-n+m] = 1;
//统计答案、输出。
    cnt = 0;
    for(int i(1);i <= m;++i)    cnt += ANS[i];
    cout << cnt << endl;
    for(int i(1);i <= m;++i)
        if(ANS[i])  printf("%d ",i);
    return 0;
}