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

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

今天错的地方是没有去重,还像条疯狗一样跑去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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

强联通分量

Kosaraju算法入门 ( 附 POJ 2186

算法详解 花了一点小时间入门了 kosaraju 算法。 记得之前在一 Read more…

强联通分量

HDU 6073 Matching In Multiplication

今天多校的第一锅…… 这套题真是神奇,明明都是Claris出的,涉及图 Read more…

强联通分量

HDU 5452 Minimum Cut

本来以为是一道好题…… 没想到xjb被我水过去了…… 题目看不大懂去找 Read more…