每个点所属的强连通分量输出有误,求助

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

ebzyl @ 2023-07-13 13:06:29

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int num;//当前已经dfs了num个点 
int dfn[maxn];//dfn[i] 第i个点是第几个被dfs到的 
int low[maxn];
vector<int> z[maxn];
void add_edge(int p1,int p2){
    z[p1].push_back(p2);
}
bool jzy[maxn];
//low[i]代表
//从i点出发 沿着回边 树边 或者 能扩大环的横叉边 走
//能走到的所有点中 dfn最小的是多少 
stack<int> s; //栈用来存储 被 dfs过 但还没有求出强连通分量的点 
bool instack[maxn];//instack[i] 代表i点是否在栈里面 
int cnt=0;//有几个强连通分量
queue<int> belong[maxn];//belong[i] 代表i点属于哪一个强连通分量 
void dfs(int i)//当前搜索到了i点
{
    num++;
    dfn[i]=low[i]=num;
    s.push(i);
    instack[i]=true;
    for (int k=0;k<z[i].size();k++)
    {
        int j = z[i][k];
        if (!dfn[j])//树边
        {
            dfs(j);
            low[i]=min(low[i],low[j]); 
        }
        else//非树边 
        {
            //这是一条回边 或者 能扩大环的横叉边 
            if (instack[j]) low[i]=min(low[i],dfn[j]);
            //if (instack[j]) low[i]=min(low[i],low[j]);
        }
    }
    if (dfn[i] == low[i])
    {
        cnt++;//多了一个强连通分量 
        while (s.top() != i)
        {
            belong[s.top()].push(cnt);
            instack[s.top()] = false;
            s.pop();
        }
        s.pop();
        instack[i]=false;
        belong[i].push(cnt);
    }
} 
int n,m;
int main()
{
    cin >> n >> m;
    for (int i=1;i<=m;i++)
    {
        int p1,p2;
        cin >> p1 >> p2;
        add_edge(p1,p2);
    }
    for (int i=1;i<=n;i++)
        if (!dfn[i]) dfs(i);
    cout<<cnt<<'\n';
    for(int i=1;i<=n;i++){
        while(belong[i].size()!=0){
            if(jzy[belong[i].front()]==false){
                jzy[belong[i].front()]==true;
                cout<<belong[i].front()<<' ';
            }
            belong[i].pop();
        }
        cout<<'\n';
    }
}

输出有问题,求调


|