#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <vector> #include <map> #include <queue> #include <set> #include <algorithm> using namespace std; #define MAXN 2001 #define MAXM 2000000 int head[MAXN]; int tot; struct Edge { int to,next; }edge[MAXM]; void init(){ tot=0; for(int i=0;i<MAXN;i++)head[i]=-1; } void Add_edge(int u,int v) { edge[tot].next=head[u]; edge[tot].to=v; head[u]=tot; ++tot; } int dfn[MAXN],low[MAXN],pre[MAXN],n,m; int times=0,top; char flag[MAXN][MAXN]; void tarjan_3(int u){ dfn[u]=low[u]=++times; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(!dfn[v]){ pre[v]=u; tarjan_3(v); low[u]=min(low[u],low[v]); } else if(pre[u]!=v) low[u]=min(low[u],dfn[v]); } } void solve(){ times=0; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(pre,0,sizeof(pre)); tarjan_3(1); for(int i=1;i<=n;i++){ if(pre[i]>0&&dfn[pre[i]]<low[i]){ printf("%d %d %d\n",pre[i],i,2); flag[pre[i]][i]=flag[i][pre[i]]=3; } } top=times=0; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(pre,0,sizeof(pre)); void tarjan(int ); for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i);
} void tarjan(int u){ dfn[u]=low[u]=++times; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(flag[u][v]==3)continue; if(!dfn[v]){ pre[v]=u; tarjan(v); low[u]=min(low[u],low[v]); if(flag[u][v]==2){ if(dfn[u]>=low[u]){ printf("%d %d %d\n",u,v,1); flag[v][u]=0; } else { printf("%d %d %d\n",v,u,1); flag[u][v]=0; } } } else if(pre[u]!=v) { if(flag[v][u]==2)printf("%d %d %d\n",u,v,1); flag[u][v]=0; low[u]=min(low[u],dfn[v]); } } } int main() { while(~scanf("%d%d",&n,&m)){ init(); memset(flag,0,sizeof(flag)); for(int i=0;i<m;i++){ int x,y; int val; scanf("%d%d%d",&x,&y,&val); if(val==1){ Add_edge(x,y); Add_edge(y,x); flag[x][y]=1; flag[y][x]=3; } else { Add_edge(x,y); Add_edge(y,x); flag[x][y]=flag[y][x]=2; } } solve(); } return 0; }
|