改为用Kosaraju求SSCC++98：#includealgorithm#includeiostream#includecstring#includecstdio#includecmathusing namespace std;const int MAXN=2e3+5MAXM=MAXNMAXN;int nmtotheadMAXN;struct Edge int tonxt; Edge to=n

#include #include #include #include #include using namespace std;

const int MAXN=2e3+5,MAXM=MAXN*MAXN; int n,m,tot,head[MAXN]; struct Edge{ int to,nxt; Edge(){ to=nxt=0; } Edge(int x,int y){ to=x,nxt=y; } } edge[MAXM];

void Add(int u,int v){ edge[++tot]={v,head[u]}; head[u]=tot; }

int top,cnt,dfc,dfn[MAXN],low[MAXN],stck[MAXN]; bool vis[MAXN];

void dfs(int u){ dfn[u]=low[u]=++dfc; stck[++top]=u; vis[u]=true; for(int i=head[u];i!=0;i=edge[i].nxt){ int v=edge[i].to; if(!dfn[v]){ dfs(v); low[u]=min(low[u],low[v]); } else if(vis[v]){ low[u]=min(low[u],low[v]); } } if(dfn[u]==low[u]){ cnt++; for(int v=stck[top];top--;v=stck[top]){ vis[v]=false; if(u==v) return ; } } }

void kosaraju(){ memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); memset(vis,false,sizeof vis); cnt=dfc=top=0; for(int i=1;i<=n&&cnt<2;i++){ if(!dfn[i]) dfs(i); } printf("%d\n",cnt==1); }

int main(){ for(scanf("%d%d",&n,&m);n||m;scanf("%d%d",&n,&m)){ memset(head,0,sizeof head); tot=0; while(m--){ int u,v; scanf("%d%d",&u,&v); int op; scanf("%d",&op); if(op==1) Add(u,v); else Add(u,v),Add(v,u); } kosaraju(); } return 0; }