GoldenPotato137的小屋
  • 留言板
  • PCB信仰尺
  • IP签名图
GoldenPotato的ACM小屋
一名HITer/LLer/ACMer的ACM(前OI)博客
  1. 首页
  2. 图论
  3. 正文

UVA610 Street Directions

2019年04月09日 488点热度 0人点赞 0条评论

题面

UVA610 Street Directions


Solution

先来解释一下题面意思:我们现在有一个联通的无向图,我们要把整个图改造为有向图,在保证强连通的情况下使得双向边尽可能少。

我们不妨思考一下:如果一条双向边被我们改造为了单向边,会导致某一个方向上的断开。因此,我们先对原图做边双缩点,桥边是不可能被改造为单向边的(因为改造后直接导致边双间不能互相联通)。除了桥边之外,其他边都是可以改造为单向边的。

因此,我们可以在每一个边双里面做一个dfs来连单向边,桥边直接连上双向边即可。

时间复杂度$O(n)$
就酱,这题就被我们切掉啦ヾ(●´∀`●)


Code

//Luogu  UVA610 Street Directions
//Apr,9th,2019
//Tarjan求点双
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
long long read()
{
    long long x=0,f=1; char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int N=1000+10;
vector <int> e[N],e2[N];
int dfn[N],dfn_to,low[N],mstack[N],top,belong[N],cnt;
bool vis[N],InStack[N];
void Tarjan(int now,int father)
{
    vis[now]=InStack[now]=true;
    mstack[++top]=now;
    dfn[now]=low[now]=++dfn_to;
    for(int i=0;i<int(e[now].size());i++)
        if(vis[e[now][i]]==false)
        {
            Tarjan(e[now][i],now);
            low[now]=min(low[now],low[e[now][i]]);
        }
        else if(e[now][i]!=father and InStack[e[now][i]]==true)
            low[now]=min(low[now],dfn[e[now][i]]);
    if(low[now]==dfn[now])
    {
        cnt++;
        while(mstack[top+1]!=now)
            InStack[mstack[top]]=false,
            belong[mstack[top--]]=cnt;
    }
}
int Find(int now,int x)
{
    for(int i=0;i<int(e[now].size());i++)
        if(e[now][i]==x)
            return i;
    return -1;
}
void dfs2(int now)
{
    if(vis[now]==true) return;
    vis[now]=true;
    for(int i=0;i<int(e[now].size());i++)
        if(belong[e[now][i]]==belong[now])
        {
            printf("%d %d\n",now,e[now][i]);
            e[e[now][i]][Find(e[now][i],now)]=0;
            dfs2(e[now][i]);
        }
}
int n,m;
int main()
{
    for(int o=1;;o++)
    {
        n=read(),m=read();
        if(n==0 and m==0) break;

        for(int i=0;i<=n;i++)
            e[i].clear(),e2[i].clear();
        for(int i=1;i<=n;i++)
            e[i].reserve(4),e2[i].reserve(4);
        for(int i=1;i<=m;i++)
        {
            int s=read(),t=read();
            e[s].push_back(t);
            e[t].push_back(s);
        }

        memset(vis,0,sizeof vis);
        memset(mstack,0,sizeof mstack);
        dfn_to=cnt=0;
        Tarjan(1,0);

        printf("%d\n\n",o);
        memset(vis,0,sizeof vis);
        for(int i=1;i<=n;i++)
            dfs2(i);
        for(int i=1;i<=n;i++)
            for(int j=0;j<int(e[i].size());j++)
                if(belong[i]!=belong[e[i][j]] and e[i][j]!=0)
                    printf("%d %d\n",i,e[i][j]);
        printf("#\n");
    }
    return 0;
}

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 图论
最后更新:2019年04月25日

GoldenPotato

HITer/ACMer/永远的OIer/数院/LLer/睿智的群星玩家+1000

点赞
< 上一篇
下一篇 >

文章评论

取消回复

GoldenPotato

HITer/ACMer/永远的OIer/数院/LLer/睿智的群星玩家+1000

NNEZ的Friends呢
  • %%%hzq dalao
  • 单向%%%神仙Maxwei_wzj
  • 可爱(?)的ComputerEngine 学弟
  • 安心退役的(?)wpy dalao
  • 把我按在地上锤的lizbaka julao
外校的Friends呢
  • %%% OItby
  • %%%神仙 冒泡ioa
  • %%%神仙attack204
  • allenyou
  • ChenHacker's Blog
  • Chhokmah姐姐() 的博客
  • CpZhao
  • stO神仙 gzy Orz
  • Woshiluo's Notebook
  • 可爱的suqingnian dalao
文章归档
  • 29
  • 18
  • 79,005
  • 22,843

COPYRIGHT © 2020 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

桂ICP备20002051号