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

定向

• 时间限制：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一遍得到边的方向。

代码

#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 星期一