强联通分量

CodeForces 864F Cities Excursions

Posted on

对Tarjan的算法理解有点要求的题,之前看了一下思路,敲了一下结果没过,照着博客改动了一下但并没有搞懂,今天补上。

题意:
给你一个有向图,若干询问,询问为从 s 到 t 的最小字典序路径中,第 k 个点是哪个点。

思路:
首先询问很多,有$4\times10^5$个询问,直接一个一个找肯定是不行的。
但是值得注意的是,点数比较少,只有$3000$个,假如我们固定起点,遍历全图来获得路径,在遍历的同时,对每一个点来记录答案。理想复杂度为$O(N^2)$,时间上满足条件。

一个问题是如何保证字典序最小,emmmm
用vector记录整张图,对于每个点的边进行排序,因为每个点访问一次,解决之。

这题还有一个合理的大坑,如果在遍历的时候,在之前已经出现了一个环,那么之后的所有点就都不会被访问。
当然你不能在找到一个环后,后面的点就不再遍历,这样会使最小字典树发生变化,会导致错误答案。
好题啊。

以上。

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 3e3 + 5;
const int maxq = 4e5 + 5;

struct Item {
    int u, v, q, id;
    bool operator<(const Item& item) const { return u < item.u; }
} items[maxq];

int dfn[maxn], low[maxn], vis[maxn], vtm;
int path[maxn], ans[maxq];
vector<int> G[maxn];
vector<Item> qary[maxn];

void tarjan(int u, int dep, bool cant)
{
    path[dep] = u;
    low[u] = dfn[u] = ++vtm;
    vis[u] = 1;
    int sz = qary[u].size();
    if (!cant)
        each(i, sz)
        {
            Item& item = qary[u][i];
            if (item.q <= dep)
                ans[item.id] = path[item.q];
        }
    sz = G[u].size();
    each(i, sz)
    {
        int v = G[u][i];
        if (!vis[v]) {
            tarjan(v, dep + 1, cant | (low[u] < dfn[u]));
            low[u] = min(low[u], low[v]);
            cant |= (low[v] < dfn[v]);
        } else if (vis[v] == 1)
            low[u] = min(low[u], dfn[v]);
    }
    vis[u] = 2;
}

int main()
{
    int n, m, q, u, v;
    scanf("%d %d %d", &n, &m, &q);
    each(i, m)
    {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
    }
    range(i, 1, n) sort(G[i].begin(), G[i].end());
    each(i, q)
    {
        Item& item = items[i];
        scanf("%d %d %d", &item.u, &item.v, &item.q);
        item.id = i;
    }
    sort(items, items + q);
    fill(ans, -1);
    each(i, q)
    {
        Item& item = items[i];
        qary[item.v].push_back(item);
        if (i == q - 1 || item.u != items[i + 1].u) {
            vtm = 0, fill(vis, 0);
            tarjan(item.u, 1, false);
            range(j, 1, n) qary[j].clear();
        }
    }
    each(i, q) printf("%d\n", ans[i]);
    return 0;
}
LCA

POJ 3728 The merchant

Posted on

LCA 好题!

这道题我暂时只知道用Tarjan的解法。
Tarjan解法完美地运用了Tarjan的核心原理与性质:
深度优先搜索时的向下局部性。自己乱取得,蛤蛤蛤

题意:
给你一棵树,每个节点有一个权值。给你很多个询问,每个询问两个点。要你在给定点的树链上找到有序的最大差值。

思路:
首先考虑分治。设树链 u -> lca -> v
答案无非只有三种情况:

  1. u -> lca 的最大差值
  2. lca -> v 的最大差值
  3. lca -> v 的最大值 - u -> lca 的最小值

考虑dp维护这四个值。
因为运用Tarjan算法的时候,基于dfs,在你的眼里,当前节点就是向下整棵树的根节点,你完全不会去考虑往上的节点。
所以你现在使用的四个值,刚好是你当前节点的孩子节点的最优值。
基于这个事实,我们可以对其状态转移并维护。

AC Code

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;

int n;
int val[maxn], res[maxn];
int up[maxn], down[maxn], max_val[maxn], min_val[maxn];
int root[maxn];
bool vis[maxn];

vector<int> g[maxn];
vector<pii> q[maxn];
vector<pii> ans[maxn];

int findRoot(int x)
{
    if (root[x] == x)
        return x;
    int fa = root[x];
    root[x] = findRoot(root[x]);
    up[x] = max(up[x], max(up[fa], max_val[fa] - min_val[x]));
    down[x] = max(down[x], max(down[fa], max_val[x] - min_val[fa]));
    max_val[x] = max(max_val[x], max_val[fa]);
    min_val[x] = min(min_val[x], min_val[fa]);
    return root[x];
}

void tarjan(int u)
{
    root[u] = u;
    vis[u] = true;
    int sz = q[u].size();
    for (int i = 0; i < sz; i++) {
        int v = q[u][i].second;
        if (vis[v]) {
            int lca = findRoot(v);
            ans[lca].push_back(make_pair(u, i));
        }
    }
    sz = g[u].size();
    for (int i = 0; i < sz; i++) {
        int v = g[u][i];
        if (!vis[v]) {
            tarjan(v);
            root[v] = u;
        }
    }
    sz = ans[u].size();
    for (int i = 0; i < sz; i++) {
        int x = ans[u][i].first, y = q[x][ans[u][i].second].second;
        int id = q[x][ans[u][i].second].first;
        if (id < 0) {
            id = -id;
            swap(x, y);
        }
        findRoot(x), findRoot(y);
        res[id] = max(up[y], down[x]);
        res[id] = max(res[id], max_val[x] - min_val[y]);
    }
}

void init()
{
    for (int i = 0; i <= n; i++) {
        g[i].clear(), q[i].clear(), ans[i].clear();
        vis[i] = false;
        up[i] = down[i] = 0;
    }
}

int main()
{
    int u, v, qnum;
    while (scanf("%d", &n) != EOF) {
        init();
        for (int i = 1; i <= n; i++) {
            scanf("%d", val + i);
            min_val[i] = max_val[i] = val[i];
        }
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        scanf("%d", &qnum);
        for (int i = 1; i <= qnum; i++) {
            scanf("%d %d", &u, &v);
            q[u].push_back(make_pair(-i, v));
            q[v].push_back(make_pair(i, u));
        }
        tarjan(1);
        for (int i = 1; i <= qnum; i++)
            printf("%d\n", res[i]);
    }
    return 0;
}
强联通分量

HDU 6165 FFF at Valentine

Posted on

好烦,感觉自己的图论知识都有了,但是一旦写起来还是非常欠缺……
什么时候我才能踩完所有的坑,成就大佬之路呢……

今天多校的第二道签到题……
是的,签到题……但是我没有写出来为什么呢……我也想知道为什么我老是会这样那样的地方写错……

今天错的地方是没有去重,还像条疯狗一样跑去BC官方博客理论了……
在这里先道个歉……
但是题解的确没写清楚

题意:
给你一个有向图,有环,无重边,无自环。
问你是否存在两个不联通的点。

思路:
拿到题的第一思路,拓扑排序,有环就缩点呗!
然后开始疯狂WA……

思路没错,但是在缩点后没有去重,导致缩点后一条边的出度增加,拓扑排序失败……

好烦……讲道理缩点+拓扑,虽然简单,但也没有沦落到这种比赛的签到题上……

原因就是数据很小,允许 \( O ( n^2 ) \)解题……
可能因为图论学傻了,没想到也不愿意用暴力做……

暴力的方法是,枚举每一个点,记录它可以达到的点,构成一个二维矩阵,然后遍历一下矩阵,看是否存在相互不可达的点即可。
虽然暴力在我眼里有点不齿,但是优雅的暴力还是非常值得认可的。

缩点 + 拓扑排序 AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

const int maxn = 1005;

int idx, n, m, scc, top, vis_time;
int head[maxn], dfn[maxn], low[maxn], in[maxn], color[maxn], st[maxn];
bool instack[maxn];

struct node {
    int to;
    int nxt;
} edges[7000];

bool g[maxn][maxn];
int deg[maxn];
int vex[maxn];

bool toposort()
{
    for (int i = 1; i <= scc; i++)
        for (int j = 1; j <= scc; j++)
            g[i][j] = false;
    for (int u = 1; u <= n; u++) {
        int cu = color[u];
        for (int id = head[u]; ~id; id = edges[id].nxt) {
            int cv = color[edges[id].to];
            if (cu != cv && !g[cu][cv]) { //这里要去重!!!
                deg[cv]++;
                g[cu][cv] = true;
            }
        }
    }
    queue<int> que;
    for (int i = 1; i <= scc; i++)
        if (deg[i] == 0)
            que.push(i);
    while (!que.empty()) {
        if (que.size() > 1)
            return true;
        int u = que.front();
        que.pop();
        for (int i = 1; i <= scc; i++) {
            if (g[u][i]) {
                if (--deg[i] == 0)
                    que.push(i);
            }
        }
    }
    return false;
}

void addEdge(int u, int v)
{
    edges[idx].to = v;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

void tarjan(int u)
{
    int v;
    low[u] = dfn[u] = ++vis_time;
    instack[u] = true;
    st[++top] = u;
    for (int id = head[u]; ~id; id = edges[id].nxt) {
        v = edges[id].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (instack[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        scc++;
        do {
            v = st[top--];
            instack[v] = false;
            color[v] = scc;
        } while (v != u);
    }
}

void init()
{
    for (int i = 0; i <= n; i++) {
        head[i] = -1;
        deg[i] = in[i] = dfn[i] = low[i] = 0;
    }
    vis_time = top = idx = scc = 0;
}

int main()
{
    int T, u, v;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        init();
        while (m--) {
            scanf("%d %d", &u, &v);
            addEdge(u, v);
        }
        for (int i = 1; i <= n; i++)
            if (dfn[i] == 0)
                tarjan(i);
        if (toposort())
            puts("Light my fire!");
        else
            puts("I love you my love and our love save us!");
    }
    return 0;
}
稳定婚姻问题

POJ 1904 King’s Quest

Posted on

由已知婚姻匹配求出所有可出轨匹配。
因为稳定婚姻问题中的匹配都是完美匹配,因此也可以换一种说法,已知一个完美匹配,求出所有完美匹配。

这道题或许可能是我这辈子做的最后一道稳定婚姻问题……因为本来出的就少,感觉都是套路……
求稳定婚姻就是模拟的板子,判定和所有出轨匹配就是tarjan缩点……

尽管如此,但还是不得不学啊……

题意:
一个国王有很多个儿子,这些儿子有很多个喜欢的女孩。国王把这些女孩都找了过来,刚好儿子和女孩的数量相同。所以只能一夫一妻了。
国王要大臣给个可行方案,大臣给了。国王又要所有可行方案。大臣就烧脑子了。

儿子最多2000个……囧……厉害厉害

思路:
其实方法的话……基本还是和稳定婚姻的判定是一样的。稳定婚姻判定点这里
在求出所有强联通分量之后,找出男性的所有可婚配配偶 和 与他在同一个强联通分量的女性的交集。
从小到大输出这个交集就是我们要求的答案。

AC Code ( 时间略长……

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 4005;
const int maxm = 2e5 + maxn + 5;

int n, m;

int head[maxn], idx;
struct node {
    int to;
    int next;
} edges[maxm];

void addEdge(int u, int v)
{
    edges[idx] = (node){ v, head[u] };
    head[u] = idx++;
}

int scc, top, vis_time;
int dfn[maxn], low[maxn], in[maxn], color[maxn], st[maxn], ans[maxn];
bool instack[maxn];

void init()
{
    for (int i = 0; i <= 2 * n; i++) {
        head[i] = -1;
        in[i] = dfn[i] = low[i] = 0;
    }
    vis_time = top = idx = scc = 0;
}

void tarjan(int u)
{
    int v;
    low[u] = dfn[u] = vis_time++;
    instack[u] = true;
    st[++top] = u;
    for (int id = head[u]; ~id; id = edges[id].next) {
        v = edges[id].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (instack[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        scc++;
        do {
            v = st[top--];
            instack[v] = false;
            //color_num[scc]++;
            color[v] = scc;
        } while (v != u);
    }
}

int main()
{
    int v;
    while (scanf("%d", &n) != EOF) {
        init();
        range(i, 1, n)
        {
            scanf("%d", &m);
            each(j, m)
            {
                scanf("%d", &v);
                addEdge(i, v + n);
            }
        }
        range(i, 1, n)
        {
            scanf("%d", &m);
            addEdge(m + n, i);
        }
        range(i, 1, 2 * n) if (dfn[i] == 0) tarjan(i);
        range(i, 1, n)
        {
            int num = 0, c = color[i];
            for (int id = head[i]; ~id; id = edges[id].next)
                if (c == color[edges[id].to])
                    ans[num++] = edges[id].to - n;
            sort(ans, ans + num);
            printf("%d", num);
            reach(i, num) printf(" %d", ans[i]);
            puts("");
        }
    }
    return 0;
}
稳定婚姻问题

BZOJ 2140 稳定婚姻

Posted on

稳定婚姻的判定问题。

老实说,写了几题后发现稳定婚姻问题几乎都是板子题……囧……
而且我作为入门题写的那道题好歹还披了一件外套,有几道完完全全的裸题写得我是非常的空虚……

回到这道题,这道题应该算是稳定婚姻判定的裸题了。
假如我们再次无脑套模板,复杂度还是在\( O(n^2) \)左右。
我们从另一个角度来考虑。如果我可以找到一个相互出轨的夫妻,那就是不稳定的。
从而,对于一个已知的婚姻匹配,如果存在一对夫妻离婚,但不会对其他夫妻造成任何影响,那么这组婚姻匹配就是稳定的。
稳定婚姻的判定就是通过这种方式找到可以相互出轨的夫妻。

一个可行解法就是求强联通分量。对于已知匹配建立好单向二分图,对于可出轨匹配用反向边表示。然后求一下强联通分量。如果存在一组匹配,他们被染色的数量超过 \( 1 \) 是什么颜色呢??
那这个婚姻匹配就是不稳定的。
复杂度为Tarjan的复杂度,估计在\( O( n ) \) 左右。

题意:
先给你一组婚姻匹配,再给你几组可出轨匹配,问你对于每一对夫妻,他们的匹配是否安全。

思路:
裸题啦,裸题,看了我上面的陈述就知道该怎么写了。

AC Code

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 8005;
const int maxm = 3e4 + 5;

int n, m;

map<string, int> man, woman;
string rman[maxn], rwoman[maxn];

int head[maxn], idx;
struct node {
    int to;
    int next;
} edges[maxm];

void addEdge(int u, int v)
{
    edges[idx] = (node){ v, head[u] };
    head[u] = idx++;
}

int scc, top, vis_time;
int dfn[maxn], low[maxn], in[maxn], color[maxn], st[maxn], color_num[maxn];
bool instack[maxn];

void init()
{
    man.clear(), woman.clear();
    for (int i = 0; i <= 2 * n; i++) {
        head[i] = -1;
        in[i] = dfn[i] = low[i] = 0;
    }
    vis_time = top = idx = scc = 0;
}

void tarjan(int u)
{
    int v;
    low[u] = dfn[u] = vis_time++;
    instack[u] = true;
    st[++top] = u;
    for (int id = head[u]; ~id; id = edges[id].next) {
        v = edges[id].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (instack[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        color_num[++scc] = 0;
        do {
            v = st[top--];
            instack[v] = false;
            color_num[scc]++;
            color[v] = scc;
        } while (v != u);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    string u, v;
    while (cin >> n) {
        init();
        range(i, 1, n)
        {
            cin >> rwoman[i] >> rman[i];
            man[rman[i]] = i;
            woman[rwoman[i]] = i;
            addEdge(i + n, i);
        }
        cin >> m;
        range(i, 1, m)
        {
            cin >> u >> v;
            addEdge(woman[u], man[v]);
        }
        range(i, 1, 2 * n) if (dfn[i] == 0) tarjan(i);
        range(i, 1, n) if (color_num[color[i]] == 1) puts("Safe");
        else puts("Unsafe");
    }
    return 0;
}
强联通分量

HDU 5452 Minimum Cut

Posted on

本来以为是一道好题……

没想到xjb被我水过去了……

题目看不大懂去找题解看题意,都说什么LCA,醉了……真的不喜欢数据弱的题目。

题意:
给你一棵生成树,再多给你几条边,要你只能删除一条生成树的边的同时,最少删掉多少条边才能使得整张图图不联通。

思路:
一个很显然的规律就是,找到生成树上度数为1的点,再比较其他度数和即可……

这里有个漏洞,就是可以在删掉一条生成树上的边就可以分割整张图,简单说,就是桥……

不是很懂他们LCA的思路,水过了就不想思考了。我倒是觉得,直接tarjan缩点预处理一下,再特判一下缩点后的点数即可。

AC Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int maxn = 2e4 + 5;
const int maxm = 2e5 + 5;
const int inf = 0x3f3f3f3f;

int tree_degree[maxn];
int degree[maxn];
int n, m;

int main()
{
    int T, u, v;
    scanf("%d", &T);
    each(cas, T)
    {
        scanf("%d %d", &n, &m);
        fill(tree_degree, 0), fill(degree, 0);
        int ans = inf;
        each(i, n - 1) scanf("%d %d", &u, &v), tree_degree[u]++, tree_degree[v]++;
        each(i, m - n + 1) scanf("%d %d", &u, &v), degree[u]++, degree[v]++;
        range(i, 1, n) if (tree_degree[i] == 1) ans = min(ans, 1 + degree[i]);
        printf("Case #%d: %d\n", cas + 1, ans);
    }
    return 0;
}