admin管理员组文章数量:1602098
Road Construction
卡了一天多,我决定先放一放,主要是对 Tarjan 的代码实现还不是很理解,所以这道题只能转载一个讲得清楚的题解了:【图的连通性】建造道路Road Construction
然后下面是里面的 AC 代码(自己写了一遍):
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int head[1200], cnt, index1, ans;
int vis[1200], dfn[1200], low[1200], du[1200];
struct node {
int u, v, next;
}edge[100000];
void add(int u, int v) {
edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void tarjan(int u, int fa) {
low[u] = ++index1;
dfn[u] = low[u];
vis[u] = 1;
for (int i = head[u];i != -1;i = edge[i].next) {
int v = edge[i].v;
if (v == fa) continue;
if (!vis[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
}
else if (v != fa) low[u] = min(low[u], dfn[v]);
}
}
void init() {
memset(head, -1, sizeof(head));
cnt = 0;
memset(vis, 0, sizeof(vis));
memset(dfn, 0, sizeof(dfn));
index1 = 0;
ans = 0;
memset(du, 0, sizeof(du));
}
int main() {
int n, m, u, v, i, j;
cin >> n >> m;
init();
while (m--) {
cin >> u >> v;
add(u, v);//无向
add(v, u);
}
tarjan(1, -1);
for (i = 1;i <= n;i++) {
for (j = head[i];j != -1;j = edge[j].next) {
int v = edge[j].v;
if (low[v] != low[i]) du[low[i]]++;
}
}
for (i = 1;i <= n;i++) {
if (du[i] == 1) ans++;
}
cout << (ans + 1) / 2 << endl;
return 0;
}
加油吧!长路漫漫
本文标签: Roadconstruction
版权声明:本文标题:Road Construction(转载) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dianzi/1728396530a1157071.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论