MENU

牛客练习赛25 E 定向(Tarjan求无向图割边+dfs构造)

2018 年 08 月 27 日 • 阅读: 1603 • 图论阅读设置

定向

  • 时间限制:C/C++ 1秒,其他语言2秒
  • 空间限制:C/C++ 262144K,其他语言524288K
  • Special Judge, 64bit IO Format: %lld

题目描述

给一张无向图,你需要将边定向,使得定向后的有向图强连通。

输入描述:

第一行两个数n,m,表示点数和边数。接下来m行,每个两个数x,y,表示x和y之间有条边。

输出描述:

如果不存在可行方案输出一行"impossible" ;否则,输出一个长度为m的01串,描述你的方案,第i个字符为1表示输入的第i条边定向为从x到y,为0表示从y到x。

输入

3 3  
1 2  
1 3  
2 3

输出

101

说明

1->2->3->1,形成一个环 ,是强连通的。

备注

$1 ≤ n,m ≤ 10^6$ ,保证无重边自环


链接

https://www.nowcoder.com/acm/contest/158/E

题意

如题,确定无向图边的反向,使得其形成的有向图强连通,无解输出impossible

题解

dfs出一棵生成树,令所有树边从父亲指向儿子,所有返祖边从后代指向祖先。判断这样构造的有向图是否强连通即可。
正确性证明如下:
如果无向图不连通或者存在割边显然无解,否则这样构造一定是一组解。
因为考虑求割边的过程,不存在割边就意味着每个点都能走回他的祖先, 所以在这样构造的有向图里,每个点也依旧能走回他的祖先。

使用Tarjan判断是否存在桥,有桥那么无解,否则dfs一遍得到边的方向。

代码

运行结果运行时间(ms)使用内存(KB)代码长度使用语言
答案正确1120402871C++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
using namespace std;
const int maxn = 100010;
const int maxm = 100010;

struct Edge
{
    int to, next;
    bool cut; // 是否为桥
    bool used; // 是否遍历过
    int dir; // 方向
}edge[maxm<<2];

int head[maxn], tot, n, m;
int low[maxn], dfn[maxn], Stack[maxn], add_block[maxn]; // 删除一个点后增加的连通块
int Index, top;
bool Instack[maxn], cut[maxn], vis[maxn];
int bridge;

void init()
{
    memset(head, -1, sizeof(head));
    tot = 0;
}

void addedge(int u, int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    edge[tot].cut = false;
    edge[tot].used = false;
    head[u] = tot++;
}

void Tarjan(int u, int pre) // 求解无向图割点和桥
{
    int v;
    low[u] = dfn[u] = ++Index;
    Stack[top++] = u;
    Instack[u] = true;
    int son = 0;
    bool flag = true;
    for (int i = head[u]; i != -1; i = edge[i].next)
    {
        v = edge[i].to;
        if (v == pre && flag) // 重边
        {
            flag = false;
            continue;
        }
        if (!dfn[v])
        {
            son++;
            Tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) // 桥
            {
                bridge++;
                edge[i].cut = true;
                edge[i^1].cut = true;
            }
            if (u != pre && low[v] >= dfn[u]) // 割点,非树根
            {
                cut[u] = true;
                add_block[u]++;
            }
        }
        else if (low[u] > dfn[v])
            low[u] = dfn[v];
    }
    if (u == pre && son > 1) // 树根,分支数大于1
        cut[u] = true;
    if (u == pre)
        add_block[u] = son - 1;
    Instack[u] = false;
    top--;
}

void dfs(int u)
{
    for (int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].to;
        if (edge[i].used) // 边已访问
            continue;
        edge[i].used = true, edge[i^1].used = true;
        edge[i].dir = 0, edge[i^1].dir = 1; // 确定关系
        dfs(v);
    }
}

void solve()
{
    memset(dfn, 0, sizeof(dfn));
    memset(Instack, 0, sizeof(Instack));
    memset(add_block, 0, sizeof(add_block));
    memset(cut, 0, sizeof(cut));
    memset(vis, 0, sizeof(vis));
    Index = top = 0;
    bridge = 0;
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (!dfn[i])
        {
            Tarjan(i, i);
            cnt++;
        }
    }
    if (cnt > 1 || bridge > 0)
        printf("impossible\n");
    else
    {
        dfs(1);
        for (int i = 0; i < tot; i += 2)
            printf("%d", edge[i].dir);
        printf("\n");
    }
}

int main()
{
    int u, v;
    while (scanf("%d%d", &n, &m) != EOF)
    {
        init();
        for (int i = 0; i < m; ++i)
        {
            scanf("%d%d", &u, &v);
            addedge(u, v);
            addedge(v, u);
        }
        solve();
    }
    return 0;
}

The end.
2018-08-27 星期一
最后编辑于: 2018 年 08 月 29 日