vector 存图 50pts 求调（悬关）

rainygame @ 2023-06-14 21:11:06

#include <bits/stdc++.h>
using namespace std;
#define MAXN 500001

int n, m, u, v, cnt;
int dfn[MAXN], low[MAXN];
vector<int> e[MAXN];
vector<vector<int>> ans;
stack<int> st;

void tarjan(int x, int las){
    low[x] = dfn[x] = ++cnt;
    st.push(x);
    for (auto i: e[x]){
        if (i == las) continue;
        if (!dfn[i]){
            tarjan(i, x);
            low[x] = min(low[x], low[i]);
        }else low[x] = min(low[x], dfn[i]);
    }
    if (dfn[x] == low[x]){
        vector<int> vec;
        vec.push_back(x);
        while (st.top() != x){
            vec.push_back(st.top());
            st.pop();
        }
        st.pop();
        ans.push_back(vec);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i(1); i<=m; ++i){
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (int i(1); i<=n; ++i){
        if (!dfn[i]) tarjan(i, 0);
    }

    cout << ans.size() << '\n';
    for (auto i: ans){
        cout << i.size() << ' ';
        for (auto j: i) cout << j << ' ';
        cout << '\n';
    }

    return 0;
}

by bzzltl @ 2023-06-15 08:26:11

@rainygame 这份代码应该是没考虑重边。 比如那个数据6输入

5 7
4 2
5 4
4 2
3 2
1 2
1 1
2 1

答案应该是

3
1 3
1 5
3 1 2 4

但是这个代码把重边直接忽视了，所以输出

5
1 5 
1 4 
1 3 
1 2 
1 1 

by bzzltl @ 2023-06-15 08:32:24

@rainygame 这道题遍历的时候还是用链式前向星写吧，因为

if (i == las) continue;

这一段会导致跳过重边。用链式前向星好写。

by bzzltl @ 2023-06-15 08:35:19

@bzzltl 因为las仅代表点的编号，所以要是遍历的边是重边的话，很可能就导致点相同而跳过，而链式前向星里面用来continue的是代表边的编号，所以不会跳过重边。

这个地方可以看看我代码

int n,m,sc,stc[N],cnt=1,ans,tot,dfn[N],low[N],head[N];
vector<int>q[N];
bool vis[N];
struct node{
    int v,nex;
}t[N];

void add(int v,int u)
{
    t[++cnt]=(node){v,head[u]};
    head[u]=cnt;
    t[++cnt]=(node){u,head[v]};
    head[v]=cnt;
}

void tarjan(int u,int in_edge)
{
    dfn[u]=low[u]=++tot;
    stc[++sc]=u;
    for(int i=head[u];i;i=t[i].nex)
    {
        if((i^1)==in_edge) continue;
        int v=t[i].v;
        if(!dfn[v])
        {
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]) vis[i]=vis[i^1]=true;
        }
        else low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]!=low[u]) return;
    ans++;
    while(stc[sc+1]!=u) q[ans].push_back(stc[sc--]);
}

by rainygame @ 2023-06-15 17:46:24

@bzzltl 所以我是要为边设一个编号，然后判断编号，对吧？

by bzzltl @ 2023-06-15 17:51:56

@rainygame 是

by bzzltl @ 2023-06-15 21:30:13

@rainygame 求关。

by rainygame @ 2023-06-15 21:35:10

@bzzltl 对对对，差点忘了，对不起啊，已关。

by bzzltl @ 2023-06-15 21:37:02

@rainygame OK