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;
}