题解：P11508 [ROIR 2017 Day 1] 数据存放

· · 题解

知识

解法

很明显这是一道有关连通分量的题目。可以发现，在同一个边双连通分量中最多有一个点属于集合 A，否则肯定不是最优的方案。

由于这是一个无向图，所以可以先 tarjan 求出强连通分量（由于无向，等价于边双）。然后缩点，可以发现这张图变成了一棵无根树。

接下来我们贪心。设强连通分量个数为 k，第 i 个连通分量中节点个数为 cnt_i。

代码

赛时代码，微丑。


// Author: chenly8128
// Created: 2025-01-05 10:52:42

#include <bits/stdc++.h>
using namespace std;
inline int read(void) {
    int res = 0;bool flag = true;char c = getchar();
    while (c < '0' || c > '9') {flag ^= (c == '-');c = getchar();}
    while (c >= '0' && c <= '9') {res = (res << 3) + (res << 1) + (c ^ 48);c = getchar();}
    return flag ? res : -res;
}
const int MAXN = 2e5+10;
int n,m,u,v,now;
int col[MAXN],dfn[MAXN],low[MAXN],cnt[MAXN],dsfa,ans;
long long ans2 = 1;
vector <int> g[MAXN];
set <int> g2[MAXN];
stack <int> s;
void tarjan(int u,int fa) {
    dfn[u] = low[u] = ++dsfa;
    s.push(u);
    for (int v : g[u]) {
        if (v == fa) continue;
        if (!dfn[v]) {
            tarjan(v,u);
            low[u] = min(low[u],low[v]);
        }
        else low[u] = min(low[u],dfn[v]);
    }
    if (dfn[u] == low[u]) {
        col[u] = ++now;
        cnt[now] = 1;
        while (s.top() != u) {
            col[s.top()] = now;
            s.pop();
            cnt[now]++;
        }
        s.pop();
    }
}
int main (void) {
    n = read();m = read();
    for (int i = 1;i <= m;i++) {
        u = read();v = read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    tarjan (1,-1);
    for (int i = 1;i <= n;i++)
        for (int j : g[i])
            if (col[j] != col[i]) g2[col[i]].insert(col[j]);
    for (int i = 1;i <= now;i++)
        if (g2[i].size() == 1) {
            ans++;
            ans2 = ans2 * cnt[i] % 1000000007;
        }
    if (ans == 0) cout << 1 << ' ' << n << '\n';
    else cout << ans << ' ' << ans2 << '\n';
    return 0;
}