NOIP模拟（10.24）T1 建设图

本文主要是介绍NOIP模拟（10.24）T1 建设图，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

建设图

题目背景：

10.24 NOIP模拟T1

分析：tarjan缩点

 

显然，本身满足双连通的部分，可以当做一个点处理，所以我们先tarjan缩一发点，然后得到了一棵树，然后我们稍加分析之后，就可以发现，只需要加入（叶子节点数 + 1） / 2条边就可以了（手动分析吧，我也不会证）

Source：

/*created by scarlyw
*/
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <set>
#include <map>
#include <vector>
#include <queue>const int MAXN = 100000 + 10;int n, x, y, m, o, top, ind, ans;
int low[MAXN], num[MAXN], dcc[MAXN], degree[MAXN];
std::vector<int> edge[MAXN], s, new_edge[MAXN];
bool vis[MAXN];inline void add_edge(int x, int y) {edge[x].push_back(y), edge[y].push_back(x);
}inline void read_in() {scanf("%d%d", &n, &m);for (int i = 1; i <= m; ++i) scanf("%d%d", &x, &y), add_edge(x, y); 
}inline void tarjan(int cur, int fa) {low[cur] = num[cur] = ++ind, vis[cur] = true, s.push_back(cur);for (int p = 0; p < edge[cur].size(); ++p) {int v = edge[cur][p];if (num[v] == 0) tarjan(v, cur), low[cur] = std::min(low[cur], low[v]);else if (vis[v] && v != fa) low[cur] = std::min(low[cur], num[v]);}if (low[cur] == num[cur]) {++top;do {o = s.back(), vis[o] = false, s.pop_back(), dcc[o] = top;} while (o != cur);}
}inline void solve() {tarjan(1, 1);if (top == 1) std::cout << "0", exit(0);for (int i = 1; i <= n; ++i)for (int p = 0; p < edge[i].size(); ++p) {int v = edge[i][p];if (dcc[v] != dcc[i]) {degree[dcc[v]]++, degree[dcc[i]]++;}}int cnt = 0;for (int i = 1; i <= top; ++i) if (degree[i] == 2) cnt++;std::cout << (cnt + 1) / 2;
}int main() {
//	freopen("graph.in", "r", stdin);
//	freopen("graph.out", "w", stdout);read_in();solve();return 0;
}

这篇关于NOIP模拟（10.24）T1 建设图的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---