我在本地运行时没有问题,不知道为什么在洛谷CE了…… 它判我对size的引用有歧义……QWQ
不知道是什么意思
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct node{int x,a,b;}r[N];
struct Edge{int ver,Next,w;}edge[N<<1],edge2[N];
int n,m,h,top,cnt,tot,tot2,tail,in[N],vis[N],que[N],ltk[N],dfn[N],low[N],sta[N],size[N],head[N],head2[N],candy[N];
long long ans;
void add(int x,int y,int z){edge[++tot].ver=y,edge[tot].w=z,edge[tot].Next=head[x],head[x]=tot;}
void add2(int x,int y,int z){in[y]++,edge2[++tot2].ver=y,edge2[tot2].w=z,edge2[tot2].Next=head2[x],head2[x]=tot2;}
void dfs(int x){
dfn[x]=low[x]=++cnt,sta[++top]=x;
for(int i=head[x];i;i=edge[i].Next)
if(!dfn[edge[i].ver]) dfs(edge[i].ver),low[x]=min(low[x],low[edge[i].ver]);
else if(!ltk[edge[i].ver]) low[x]=min(low[x],dfn[edge[i].ver]);
if(dfn[x]==low[x]){
ltk[0]++;
while(top){
ltk[sta[top]]=ltk[0],size[ltk[0]]++;
if(sta[top--]==x) break;
}
}
}
void tuopu(){
for(int i=1;i<=ltk[0];i++) if(!in[i]) que[++tail]=i,vis[i]=candy[i]=1;
while(h<tail){
int x=que[++h];
for(int i=head2[x];i;i=edge2[i].Next){
if(!--in[edge2[i].ver]) que[++tail]=edge2[i].ver,vis[edge2[i].ver]=1;
if(!edge2[i].w) candy[edge2[i].ver]=max(candy[edge2[i].ver],candy[x]+1);
else candy[edge2[i].ver]=max(candy[edge2[i].ver],candy[x]);
}
}
for(int i=1;i<=ltk[0];i++) if(!vis[i]){cout<<"-1\n";exit(0);}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>r[i].x>>r[i].a>>r[i].b;
if(r[i].x==1) add(r[i].a,r[i].b,1),add(r[i].b,r[i].a,1);
else if(r[i].x==3) add(r[i].b,r[i].a,1);
else if(r[i].x==5) add(r[i].a,r[i].b,1);
}
for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i);
for(int i=1;i<=n;i++) for(int j=head[i];j;j=edge[j].Next) if(ltk[i]!=ltk[edge[j].ver]) add2(ltk[i],ltk[edge[j].ver],1);
for(int i=1;i<=m;i++) if(r[i].x==2){
if(ltk[r[i].a]==ltk[r[i].b]){cout<<"-1";return 0;}
else add2(ltk[r[i].a],ltk[r[i].b],0);
}else if(r[i].x==4){
if(ltk[r[i].a]==ltk[r[i].b]){cout<<"-1";return 0;}
else add2(ltk[r[i].b],ltk[r[i].a],0);
}
tuopu();
for(int i=1;i<=ltk[0];i++) ans+=(candy[i]*size[i]);
cout<<ans;
return 0;
}
马蜂丑陋,不喜勿喷