80分求助,谢谢大佬Orz
查看原帖
80分求助,谢谢大佬Orz
371988
Sleeper_Liang楼主2021/11/15 17:08

用的堆排序,有两个点过不去

#include<bits/stdc++.h>
#define maxn 5005
#define maxm 50005
using namespace std;
int n,m,ans[maxn][maxn];
int num,head[5005];
struct node{
	int nex,to;
};
node e[10005];
void add(int fr,int t)//链式前项星 
{
	e[++num].to=t;
	e[num].nex=head[fr];
	head[fr]=num;
}
int dfn[maxn],low[maxn],dfs_num,stak[maxn],top,vis[maxn],color[maxn];
void tarjan(int x)
{
	dfn[x]=low[x]=++dfs_num;
	stak[++top]=x;
	vis[x]=1;
	for(int i=head[x];i;i=e[i].nex)
	{
		int j=e[i].to;
		if(!dfn[j]){
			tarjan(j);
			low[x]=min(low[x],low[j]);//tarjan的核心判断 
		}
		if(vis[j]){
			low[x]=min(low[x],dfn[j]);
		}
	}
	if(dfn[x]==low[x])
	{
		vis[x]=0;
		while(stak[top]!=x)
		{
			vis[stak[top]]=0;		//ans用来存答案,0行用来存该行的长度 		 
			ans[low[x]][++ans[low[x]][0]]=stak[top--];//其他行存该强连通分量的点
		}
		ans[low[x]][++ans[low[x]][0]]=stak[top--];
	}
	
}
priority_queue<int,vector<int>,greater<int> >q;//小根堆用来排序 
int main()
{
	cin>>n>>m;
	for(int i=1,a,b,c;i<=m;i++)
	{
		cin>>a>>b>>c;
		switch(c)
		{
			case 2:add(b,a);add(a,b);break;//判断该边类型 
			case 1:add(a,b);
		}
	}
	for(int i=1;i<=n;i++)
	if(!dfn[i])tarjan(i);
	int max_=0,j;
	for(int i=1;i<=n;i++)//搜一搜最大强连通分量 
	{
		if(!ans[i][0])continue;
		else if(ans[i][0]>max_){
			max_=ans[i][0];
			j=i;
		}
	 } 
	for(int i=1;i<=ans[j][0];i++)
	{
		q.push(ans[j][i]);//二维数组用堆来排序 
	}
	cout<<ans[j][0]<<endl;
	while(!q.empty())
	{
		cout<<q.top()<<' ';
		q.pop();
	}
	return 0;
}
2021/11/15 17:08
加载中...