小蒟蒻全WA求调

B3609 [图论与代数结构 701] 强连通分量

I_LOVE_XYN @ 2024-06-13 20:44:33

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define int long long
using namespace std;
inline int read(){
    char x = getchar();
    int l = 1,d = 0;
    while(!isdigit(x)) l = (x == '-' ? -l : l),x = getchar();
    while(isdigit(x)) d = (d << 1) + (d << 3) + x - 48,x = getchar();
    return l * d;
}
inline void write(int x){
    int cnt = 0,p[106];
    if(x < 0) putchar('-'),x = -x;
    if(!x) putchar('0');
    while(x){
        p[++cnt] = x % 10;
        x /= 10;
    }
    for(int i = cnt;i >= 1; i--) putchar(p[i] + '0');
}
const int N = 100000;
int n,m,tar,cnt,dfn[N],low[N],p[N],vis[N];
vector<int> edge[N],team[N];
stack<int> st;
void dfs(int x){
    st.push(x);
    dfn[x] = low[x] = ++cnt;
    for(auto &to : edge[x])
        if(!dfn[to]){
            dfs(to);
            low[x] = min(low[x],low[to]);
        }else if(!p[to])
            low[x] = min(low[x],dfn[to]);
    if(low[x] == dfn[x]){
        int head;
        tar++;
        do{
            head = st.top();
            st.pop();
            p[head] = tar;
            team[tar].push_back(head);
        }while(head != x);  
    }
}
signed main(){
    n = read(),m = read();
    for(int i = 1;i <= n; i++) edge[read()].push_back(read());
    for(int i = 1;i <= n; i++)
        if(!dfn[i])
            dfs(i);
    write(tar),putchar('\n');
    for(int i = 1;i <= tar; i++) sort(team[i].begin(),team[i].end());
    for(int i = 1;i <= n; i++){
        if(vis[p[i]]) continue;
        vis[p[i]] = 1;
        for(auto &to : team[p[i]])
            write(to),putchar(' ');
        putchar('\n');
    }
    return 0;
}

by Lu_xZ @ 2024-06-13 20:54:57

进栈时 p 没连带更新


by Lu_xZ @ 2024-06-13 21:03:22

@I_LOVE_XYN 看错了。

你边数写的是 n


by I_LOVE_XYN @ 2024-06-13 21:24:15

@Lu_xZ 感谢dalao,我这错误真是离谱


by I_LOVE_XYN @ 2024-06-13 21:25:03

@Lu_xZ A了,感谢


|