POJ 1438 One-way Traffic

意甲冠军：

与 http://blog.csdn.net/houserabbit/article/details/38958891 类别似仅仅不是将原本的无向图变为混合图

思路：

在上一篇我也写过了 http://blog.csdn.net/houserabbit/article/details/38958891 首先是找桥那么就须要先把混合图变成无向图由于题目说答案存在因此桥必定是混合图里的无向边

然后就是块内的工作了也是分两种边讨论仅仅只是判定边是否留下的时候要看一下它是不是原图的无向边由于有向边是不能动的最后略微改一下输出基本与上一篇一致

因此我们能够总结出一种思路对于基于删边的构造强连通图的方法——找桥+块内dfs分2种边讨论以前也以前做过基于加边的构造强连通图大致方法就是——强连通缩点+入度出度讨论

代码：

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<vector>
using namespace std;
typedef long long LL;
#define N 2010
#define M 4000010
#define inf 2147483647

int n,m,t=1,tot,idx;
int head[N],dfn[N],low[N];
struct edge
{
    int u,v,next;
    bool vis,cut,left,dir,exit;
}ed[M];

void add(int u,int v,bool dir,bool exit)
{
    ed[tot].u=u;
    ed[tot].v=v;
    ed[tot].next=head[u];
    ed[tot].vis=ed[tot].cut=ed[tot].left=false;
    ed[tot].dir=dir;
    ed[tot].exit=exit;
    head[u]=tot++;
}

void tarjan(int u)
{
    int i,v;
    dfn[u]=low[u]=++idx;
    for(i=head[u];~i;i=ed[i].next)
    {
        v=ed[i].v;
        if(ed[i].vis) continue;
		ed[i].vis=ed[i^1].vis=true;
        if(dfn[v]==-1)
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<low[v])
            {
                ed[i].cut=ed[i^1].cut=true;
                ed[i].left=ed[i^1].left=true;
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}

void dfs(int u)
{
    int i,v;
    dfn[u]=low[u]=++idx;
    for(i=head[u];~i;i=ed[i].next)
    {
        if(ed[i].cut||!ed[i].exit) continue;
        v=ed[i].v;
        if(dfn[v]==-1)
        {
            ed[i].vis=ed[i^1].vis=true;
            dfs(v);
            low[u]=min(low[u],low[v]);
            if(!ed[i].dir)
            {
                if(low[v]>dfn[u]) ed[i^1].left=true;
                else ed[i].left=true;
            }
        }
        else
        {
            low[u]=min(low[u],dfn[v]);
            if(!ed[i].vis&&!ed[i].dir) ed[i].left=true;
            ed[i].vis=ed[i^1].vis=true;
        }
    }
}

void solve()
{
	int i;
	memset(dfn,-1,sizeof(dfn));
	idx=0;
	tarjan(1);
	memset(dfn,-1,sizeof(dfn));
	idx=0;
	for(i=0;i<tot;i++) ed[i].vis=false;
	for(i=1;i<=n;i++)
    {
        if(dfn[i]==-1) dfs(i);
    }
}

int main()
{
    int i,u,v,k;
    while(~scanf("%d%d",&n,&m))
    {
        tot=0;
        memset(head,-1,sizeof(head));
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&k);
            if(k&1)
            {
                add(u,v,true,true);
                add(v,u,true,false);
            }
            else
            {
                add(u,v,false,true);
                add(v,u,false,true);
            }
        }
        solve();
        for(i=0;i<tot;i+=2)
        {
            if(ed[i].dir) continue;
            if(ed[i].left&&ed[i^1].left) printf("%d %d 2
",ed[i].u,ed[i].v);
            else if(ed[i].left) printf("%d %d 1
",ed[i].u,ed[i].v);
            else printf("%d %d 1
",ed[i].v,ed[i].u);
        }
    }
	return 0;
}