UVALive 5135 Mining Your Own Business——点双连通分量

UVALive 5135 Mining Your Own Business——点双连通分量

​

点数可能大于边数，导致用n初始化不够，TLE了两发，改了memset过了

#include using namespace std;typedef long long ll;const int maxn = 1e5 + 10;int kase, n, m;int mem, head[maxn];struct Edge { int to, next; } edges[maxn];int dfn[maxn], low[maxn], id;int tp;struct Node { int u, v; } st[maxn];int iscut[maxn];int bcc_cnt, bccid[maxn];vector bcc[maxn];void init() { mem = 0; memset(head, -1, sizeof(head)); id = tp = bcc_cnt = 0; memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(iscut, 0, sizeof(iscut)); memset(bccid, 0, sizeof(bccid));}void addedge(int u, int v) { edges[++mem].to = v; edges[mem].next = head[u]; head[u] = mem;}void tarjan(int fa, int u) { int son = 0; dfn[u] = low[u] = ++id; for (int i = head[u]; ~i; i = edges[i].next) { int v = edges[i].to; Node node = Node{u, v}; if (!dfn[v]) { son++; st[++tp] = node; tarjan(u, v); low[u] = min(low[u], low[v]); if (low[v] >= dfn[u]) { iscut[u] = 1; bcc[++bcc_cnt].clear(); while (1) { Node t = st[tp--]; if (bccid[t.u] != bcc_cnt) { bcc[bcc_cnt].push_back(t.u); bccid[t.u] = bcc_cnt; } if (bccid[t.v] != bcc_cnt) { bcc[bcc_cnt].push_back(t.v); bccid[t.v] = bcc_cnt; } if (t.u == u && t.v == v) break; } } } else if (dfn[v] < dfn[u] && v != fa) { low[u] = min(low[u], dfn[v]); st[++tp] = node; } } if (fa < 0 && son == 1) iscut[u] = 0;}int main() { while (~scanf("%d", &n) && n) { init(); m = 0; for (int i = 1; i <= n; i++) { int u, v; scanf("%d%d", &u, &v); m = max(m, max(u, v)); addedge(u, v); addedge(v, u); } swap(n, m); for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(-1, i); ll ans1 = 0, ans2 = 1; for (int i = 1; i <= bcc_cnt; i++) { int cut_cnt = 0; for (int j = 0; j < bcc[i].size(); j++) { if (iscut[bcc[i][j]]) cut_cnt++; } if (cut_cnt == 1) { ans1++; ans2 *= (ll)(bcc[i].size()-1); } } if (bcc_cnt == 1) { ans1 = 2; ans2 = (ll)bcc[1].size()*(bcc[1].size()-1)/2; } printf("Case %d: %lld %lld\n", ++kase, ans1, ans2); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。