每个点所属的强连通分量输出有误,求助
查看原帖
每个点所属的强连通分量输出有误,求助
929664
ebzyl楼主2023/7/13 13:06
#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';
	}
}

输出有问题,求调

2023/7/13 13:06
加载中...