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

#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 tarjan(int u){ // 经典 tarjan 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]) tarjan(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 solve(){ memset(head,0,sizeof head); // 清空链式前向星 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); // 双向边 } memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); memset(vis,false,sizeof vis); cnt=dfc=top=0; // 记得把栈也一起清空（top=0） for(int i=1;i<=n&&cnt<2;i++) // 判断是否找到了两个及以上的强连通分量 if(!dfn[i]) tarjan(i); printf("%d\n",cnt==1); } int main(){ while(scanf("%d%d",&n,&m),n||m) solve(); return 0; }