标签: Tarjan-SCC

[CCC2007]Road Construction 题解

[CCC2007]Road Construction 题解

题目地址:POJ:3352 — Road Construction

题目描述

It’s almost summer time, and that means that it’s almost summer construction time! This year, the good people who are in charge of the roads on the tropical island paradise of Remote Island would like to repair and upgrade the various roads that lead between the various tourist attractions on the island.
The roads themselves are also rather interesting. Due to the strange customs of the island, the roads are arranged so that they never meet at intersections, but rather pass over or under each other using bridges and tunnels. In this way, each road runs between two specific tourist attractions, so that the tourists do not become irreparably lost.
Unfortunately, given the nature of the repairs and upgrades needed on each road, when the construction company works on a particular road, it is unusable in either direction. This could cause a problem if it becomes impossible to travel between two tourist attractions, even if the construction company works on only one road at any particular time.
So, the Road Department of Remote Island has decided to call upon your consulting services to help remedy this problem. It has been decided that new roads will have to be built between the various attractions in such a way that in the final configuration, if any one road is undergoing construction, it would still be possible to travel between any two tourist attractions using the remaining roads. Your task is to find the minimum number of new roads necessary.

题意简述

有一个连通图,问至少加几条边可以让它变成一个边双连通图。

输入输出格式

输入格式:
The first line of input will consist of positive integers n and r, separated by a space, where 3 ≤ n ≤ 1000 is the number of tourist attractions on the island, and 2 ≤ r ≤ 1000 is the number of roads. The tourist attractions are conveniently labelled from 1 to n. Each of the following r lines will consist of two integers, v and w, separated by a space, indicating that a road exists between the attractions labelled v and w. Note that you may travel in either direction down each road, and any pair of tourist attractions will have at most one road directly between them. Also, you are assured that in the current configuration, it is possible to travel between any two tourist attractions.

输出格式:
One line, consisting of an integer, which gives the minimum number of roads that we need to add.

输入输出样例

输入样例#1:

10 12
1 2
1 3
1 4
2 5
2 6
5 6
3 7
3 8
7 8
4 9
4 10
9 10

输出样例#1:

2

输入样例#2:

3 3
1 2
2 3
1 3

输出样例#2:

0

题解

先对边双缩点,缩点后的边双是一棵树,只要把树上的叶子两两连起来就可以把链合并成一个环,成为更大的边双。因此答案是(叶子数量+1)/2。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 10005;

int n, m;
std::vector<int> gra[MAXN];

int dfn[MAXN], low[MAXN], clk, deg[MAXN];

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++clk;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(v == fa) continue;
        if(!dfn[v]) {
            tarjan(v, u);
            low[u] = std::min(low[u], low[v]);
        } else {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
}

int main() {
    n = readint(); m = readint();
    for(int i = 1, u, v; i <= m; i++) {
        u = readint(); v = readint();
        gra[u].push_back(v);
        gra[v].push_back(u);
    }
    tarjan(1, 0);
    for(int u = 1; u <= n; u++) {
        for(int i = 0; i < gra[u].size(); i++) {
            int v = gra[u][i];
            if(low[u] != low[v]) {
                deg[low[u]]++;
            }
        }
    }
    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        if(deg[i] == 1) cnt++;
    }
    printf("%d", (cnt + 1) / 2);
    return 0;
}
[USACO5.3]校园网Network of Schools 题解

[USACO5.3]校园网Network of Schools 题解

题目地址:洛谷:【P2746】[USACO5.3]校园网Network of Schools – 洛谷

题目描述

一些学校连入一个电脑网络。那些学校已订立了协议:每个学校都会给其它的一些学校分发软件(称作“接受学校”)。注意即使 B 在 A 学校的分发列表中, A 也不一定在 B 学校的列表中。
你要写一个程序计算,根据协议,为了让网络中所有的学校都用上新软件,必须接受新软件副本的最少学校数目(子任务 A)。更进一步,我们想要确定通过给任意一个学校发送新软件,这个软件就会分发到网络中的所有学校。为了完成这个任务,我们可能必须扩展接收学校列表,使其加入新成员。计算最少需要增加几个扩展,使得不论我们给哪个学校发送新软件,它都会到达其余所有的学校(子任务 B)。一个扩展就是在一个学校的接收学校列表中引入一个新成员。

输入输出格式

输入格式:
输入文件的第一行包括一个整数 N:网络中的学校数目(2 <= N <= 100)。学校用前 N 个正整数标识。
接下来 N 行中每行都表示一个接收学校列表(分发列表)。第 i+1 行包括学校 i 的接收学校的标识符。每个列表用 0 结束。空列表只用一个 0 表示。

输出格式:
你的程序应该在输出文件中输出两行。
第一行应该包括一个正整数:子任务 A 的解。
第二行应该包括子任务 B 的解。

输入输出样例

输入样例#1:

5
2 4 3 0
4 5 0
0
0
1 0

输出样例#1:

1
2

题解

由于强连通分量内部的点两两互达,不需要考虑内部的情况,直接缩点。对于子任务A,答案就是缩点后入度为0的点的数量,因为当所有入度为0的点都被分发了,入度大于0的点也会被分发,反过来说,如果只分发给入度大于0的点,入度为0的点永远不会被分发到。对于子任务B,考虑只需要从出度为0的点向入度为0的点连边即可,因此答案是出度为0的点的数量和入度为0的点的数量的较大值。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>
#include <stack>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 105;

int n, m;

std::vector<int> gra[MAXN];

int dfn[MAXN], low[MAXN], sno[MAXN], scc, clk;
std::stack<int> sta;
bool insta[MAXN];

inline void tarjan(int u) {
    dfn[u] = low[u] = ++clk;
    insta[u] = true; sta.push(u);
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if(insta[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        scc++;
        int p;
        do {
            p = sta.top(); sta.pop(); insta[p] = false;
            sno[p] = scc;
        } while(p != u);
    }
}

int ind[MAXN], outd[MAXN];

int v;

int main() {
    n = readint();
    for(int u = 1; u <= n; u++) {
        for(;;) {
            v = readint(); if(!v) break;
            gra[u].push_back(v);
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) tarjan(i);
    }
    for(int u = 1; u <= n; u++) {
        for(int i = 0; i < gra[u].size(); i++) {
            int v = gra[u][i];
            if(sno[u] != sno[v]) {
                outd[sno[u]]++;
                ind[sno[v]]++;
            }
        }
    }
    if(scc == 1) {
        puts("1\n0");
        return 0;
    }
    int out0 = 0, in0 = 0;
    for(int i = 1; i <= scc; i++) {
        if(!ind[i]) in0++;
        if(!outd[i]) out0++;
    }
    printf("%d\n%d", in0, std::max(out0, in0));
    return 0;
}
[HAOI2006]受欢迎的牛 题解

[HAOI2006]受欢迎的牛 题解

题目地址:洛谷:【P2341】[HAOI2006]受欢迎的牛 – 洛谷、BZOJ:Problem 1051. — [HAOI2006]受欢迎的牛

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂,每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜欢B,B喜欢C,那么A也喜欢C。牛栏里共有N 头奶牛,给定一些奶牛之间的爱慕关系,请你算出有多少头奶牛可以当明星。

输入输出格式

输入格式:
第一行:两个用空格分开的整数:N和M
第二行到第M + 1行:每行两个用空格分开的整数:A和B,表示A喜欢B

输出格式:
第一行:单独一个整数,表示明星奶牛的数量

输入输出样例

输入样例#1:

3 3
1 2
2 1
2 3

输出样例#1:

1

说明

只有 3 号奶牛可以做明星
【数据范围】
10%的数据N<=20, M<=50
30%的数据N<=1000,M<=20000
70%的数据N<=5000,M<=50000
100%的数据N<=10000,M<=50000

题解

Tarjan缩点练手。
同一SCC内的所有点都可以互达,因此不用考虑SCC内的情况,直接缩点解决。考虑出度问题,只有当一个点作为一棵叶子到根的有向树的树根时才有答案,因此有多棵树的情况是无解的。考虑出度,如果出度为0的点有两个则答案为0,如果只有一个该SCC的大小就是答案。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <utility>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 10005;

int n, m;

std::vector<int> gra[MAXN], gran[MAXN];
int deg[MAXN];

int dfn[MAXN], low[MAXN], sno[MAXN], clk, scc;
std::stack<int> sta;
bool insta[MAXN];

inline void tarjan(int u) {
    dfn[u] = low[u] = ++clk;
    insta[u] = true; sta.push(u);
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if(insta[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        scc++;
        int p;
        do {
            p = sta.top(); sta.pop();
            insta[p] = false;
            sno[p] = scc;
        } while(p != u);
    }
}

std::set<std::pair<int, int> > edges;
int u, v;

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= m; i++) {
        u = readint(); v = readint();
        gra[u].push_back(v);
    }
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) tarjan(i);
    }
    for(int u = 1; u <= n; u++) {
        for(int i = 0; i < gra[u].size(); i++) {
            int v = gra[u][i];
            if(sno[u] != sno[v] && !edges.count(std::pair<int, int>(sno[u], sno[v]))) {
                edges.insert(std::pair<int, int>(sno[u], sno[v]));
                gran[sno[u]].push_back(sno[v]);
                deg[sno[u]]++;
            }
        }
    }
    int ansn = -1;
    for(int i = 1; i <= scc; i++) {
        if(!deg[i] && ansn != -1) {
            puts("0");
            return 0;
        }
        if(!deg[i] && ansn == -1) {
            ansn = i;
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        if(sno[i] == ansn) {
            ans++;
        }
    }
    printf("%d", ans);
    return 0;
}