[kuangbin带你飞]专题九 连通图

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f, N = 105, M = N * N;

int n, tot, top, num, cnt;
int ver[M], nxt[M], head[N];
int dfn[N], low[N], sta[N], insta[N], scc[N];
int ind[N], outd[N];

void add(int x, int y) {
    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}

void tarjan(int x) {
    dfn[x] = low[x] = ++num;
    sta[++top] = x;
    insta[x] = 1;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (insta[y]) low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x]) {
        cnt++;
        while (sta[top+1] != x) {
            scc[sta[top]] = cnt;
            insta[sta[top--]] = 0;
        }
    }
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    int x;
    for (int i = 1; i <= n; ++i) {
        while (cin >> x && x) add(i, x);
    }
    for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i);
    for (int i = 1; i <= n; ++i) {
        for (int j = head[i]; j; j = nxt[j]) {
            int k = ver[j];
            if (scc[i] != scc[k]) outd[scc[i]]++, ind[scc[k]]++;
        }
    }
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= cnt; ++i) {
        if (!ind[i]) cnt1++;
        if (!outd[i]) cnt2++;
    }
    if (cnt == 1) cout << "1\n0\n";
    else cout << cnt1 << '\n' << max(cnt1, cnt2) << '\n';
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f, N = 105, M = N * N;

int n, tot, num;
int ver[M], nxt[M], head[N];
int dfn[N], low[N], cut[N];

void add(int x, int y) {
    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}

void tarjan(int x, int fa) {
    dfn[x] = low[x] = ++num;
    int child = 0;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (!dfn[y]) {
            tarjan(y, x);
            low[x] = min(low[x], low[y]);
            if (dfn[x] <= low[y] && x != fa) cut[x] = 1;
            if (x == fa) child++;
        }
        else if (fa != y) low[x] = min(low[x], dfn[y]);
    }
    if (child >= 2 && x == fa) cut[x] = 1;
}

void init() {
    tot = num = 0;
    memset(head, 0, sizeof(head));
    memset(cut, 0, sizeof(cut));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
}

int main() 
{
    while (scanf("%d", &n) && n) {
        int x, y;
        init();
        while (scanf("%d", &x) && x) {
            while (getchar() != '\n') {
                scanf("%d", &y);
                add(x, y); add(y, x);
            }
        }
        for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i, i);
        int ans = 0;
        for (int i = 1; i <= n; ++i) if (cut[i]) ans++;
        printf("%d\n", ans);
    }
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f, N = 105, M = N * N;

int n, tot, num, res;
int ver[M], nxt[M], head[N];
int dfn[N], low[N], bridge[M];

void add(int x, int y) {
    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}

void tarjan(int x, int inedge) {
    dfn[x] = low[x] = ++num;
    for (int i = head[x]; i ; i = nxt[i]) {
        int y = ver[i];
        if (!dfn[y]) {
            tarjan(y, i);
            low[x] = min(low[x], low[y]);
            if (dfn[x] < low[y]) bridge[i] = bridge[i^1] = 1, res++;
        }
        else if (i != (inedge ^ 1)) low[x] = min(low[x], dfn[y]);
    }
}

void init() {
    tot = 1; num = res = 0;
    memset(head, 0, sizeof(head));
    memset(bridge, 0, sizeof(bridge));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
}

int main() 
{
    while (~scanf("%d", &n)) {
        init();
        int x, y, num;
        for (int i = 1; i <= n; ++i) {
            scanf("%d (%d)", &x, &num);
            while (num--) {
                scanf("%d", &y);
                if (y <= x) continue;
                add(x, y); add(y, x);
            }
        }
        for (int i = 0; i < n; ++i) if (!dfn[i]) tarjan(i, 0);
        printf("%d critical links\n", res);
        for (int i = 2; i < tot; i += 2) {
            if (bridge[i])
                printf("%d - %d\n", ver[i^1], ver[i]);
        }
        puts("");
    }
    return 0;
}