2次tarjan+topo算法,80分求教!
查看原帖
2次tarjan+topo算法,80分求教!
776599
jping楼主2023/8/7 18:17

tar0缩点,tarjan判断还有环则输出-1,topo出结果,80分,WA3点,求教!

#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;
const int Nm=1e5+2;
vector<int>ve[Nm],vt[Nm],ve1[Nm],vt1[Nm]; 
int vis[Nm];
ll dis[Nm];
stack<int>st;
queue<int>AA;
int dn,dfn[Nm],low[Nm],sd[Nm],cnt[Nm],in[Nm];
void tar0(int x,int fa){
	dn++;
	dfn[x]=low[x]=dn;
	vis[x]=1;
	st.push(x);
	int t;
	for(int i=0;i<ve[x].size();i++){
		t=ve[x][i];
		if(vt[x][i]>0)continue;
		if(dfn[t]==0){//树边 
			tar0(t,x);
			low[x]=min(low[x],low[t]);
		}
		else if(vis[t]==1)low[x]=min(low[x],low[t]);
	}
	int y;
	if(low[x]==dfn[x]){
		while(!st.empty()){
			y=st.top();
			st.pop();
			sd[y]=x;
			vis[y]=0;
			if(x==y)break;
		}
	}
	return;
}
int flag=1;
void tarjan(int x,int fa){
	dn++;
	dfn[x]=low[x]=dn;
	vis[x]=1;
	st.push(x);
	int t;
	for(int i=0;i<ve1[x].size();i++){
		t=ve1[x][i];
		if(dfn[t]==0){//树边 
			tarjan(t,x);
			low[x]=min(low[x],low[t]);
		}
		else if(vis[t]==1)low[x]=min(low[x],low[t]);
	}
	int num=0,y;
	if(low[x]==dfn[x]){
		while(!st.empty()){
			y=st.top();
			st.pop();
			vis[y]=0;
			num++;
			if(x==y)break;
		}
		if(num>1)flag=0;
	}
	return;
}
int main(){
	int n,m,op,u,v;	
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&op,&u,&v);
		if(op==1){
			ve[u].push_back(v);
			vt[u].push_back(0);
			ve[v].push_back(u);
			vt[v].push_back(0);
		}
		else if(op==2){
			ve[u].push_back(v);
			vt[u].push_back(1);
		}
		else if(op==3){
			ve[v].push_back(u);
			vt[v].push_back(0);
		}
		else if(op==4){
			ve[v].push_back(u);
			vt[v].push_back(1);
		}
		else{
			ve[u].push_back(v);
			vt[u].push_back(0);
		}
	}
	for(int i=1;i<=n;i++)sd[i]=i;
	for(int i=1;i<=n;i++)if(dfn[i]==0)tar0(i,0);
	int t;
	for(int i=1;i<=n;i++){
		for(int j=0;j<ve[i].size();j++){
			t=ve[i][j];
			if(sd[i]==sd[t])continue;
			ve1[sd[i]].push_back(sd[t]);
			vt1[sd[i]].push_back(vt[i][j]);
			in[sd[t]]++;
		}
	}
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(vis,0,sizeof(vis));
	while(!st.empty())st.pop();
	dn=0;
	for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i,0);
	if(flag==0){
		cout<<-1;
		return 0;
	}
	for(int i=1;i<=n;i++){
		if(in[sd[i]]==0 && dis[sd[i]]==0){
			dis[sd[i]]=1;
			AA.push(sd[i]);
		}
	}
	int now;
	while(!AA.empty()){//2e5
		now=AA.front();
		AA.pop();
		for(int i=0;i<ve1[now].size();i++){
			t=ve1[now][i];
			dis[t]=max(dis[t],dis[now]+vt1[now][i]);
			in[t]--;
			if(in[t]==0)AA.push(t);
		}
	}
	ll ans=0;
	for(int i=1;i<=n;i++)ans+=dis[sd[i]];
	cout<<ans;
	return 0;
}
2023/8/7 18:17
加载中...