E - We Need More Bosses CodeForces - 1000E （tarjan缩点，树的直径）
E - We Need More Bosses
Your friend is developing a computer game. He has already decided how the game world should look like — it should consist of nn locations connected by mm two-waypassages. The passages are designed in such a way that it should be possible to get from any location to any other location.
Of course, some passages should be guarded by the monsters (if you just can go everywhere without any difficulties, then it's not fun, right?). Some crucial passages will be guarded by really fearsome monsters, requiring the hero to prepare for battle and designing his own tactics of defeating them (commonly these kinds of monsters are called bosses). And your friend wants you to help him place these bosses.
The game will start in location ss and end in location tt, but these locations are not chosen yet. After choosing these locations, your friend will place a boss in each passage such that it is impossible to get from ss to tt without using this passage. Your friend wants to place as much bosses as possible (because more challenges means more fun, right?), so he asks you to help him determine the maximum possible number of bosses, considering that any location can be chosen as ss or as tt.
Input
The first line contains two integers nn and mm (2≤n≤3⋅1052≤n≤3⋅105, n−1≤m≤3⋅105n−1≤m≤3⋅105) — the number of locations and passages, respectively.
Then mm lines follow, each containing two integers xx and yy (1≤x,y≤n1≤x,y≤n, x≠yx≠y) describing the endpoints of one of the passages.
It is guaranteed that there is no pair of locations directly connected by two or more passages, and that any location is reachable from any other location.
Output
Print one integer — the maximum number of bosses your friend can place, considering all possible choices for ss and tt.
Examples
Input
5 51 22 33 14 15 2
Output
2
Input
4 31 24 33 2
Output
3
题意：
给你一个无向图，让你招到一个路径，这条路径中”桥“最多。
输出最多的桥的数量。
思路：
直接用tarjan强连通缩点后建树，然后树的直径就是答案。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2) { ans = ans * a % MOD; } a = a * a % MOD; b /= 2;} return ans;}
inline void getInt(int *p);
const int maxn = 700010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
const int MAXN = maxn;
const int MAXM = maxn;
struct Edge {
int to, next;
bool cut;
} edge[MAXM];
int head[MAXN], tot;
int Low[MAXN], DFN[MAXN], Stack[MAXN], Belong[MAXN]; //Belong数组的值是1~block
int Index, top;
int block;
bool Instack[MAXN];
int bridge;
void addedge(int u, int v)
{
edge[tot].to = v; edge[tot].next = head[u]; edge[tot].cut = false;
head[u] = tot++;
}
void Tarjan(int u, int pre)
{
int v;
Low[u] = DFN[u] = ++Index;
Stack[top++] = u;
Instack[u] = true;
for (int i = head[u]; i != -1; i = edge[i].next) {
v = edge[i].to;
if ( v == pre ) { continue; }
if ( !DFN[v] ) {
Tarjan(v, u);
if (Low[u] > Low[v]) { Low[u] = Low[v]; }
if (Low[v] > Low[u]) {
bridge++;
edge[i].cut = true;
edge[i ^ 1].cut = true;
}
} else if (Instack[v] && Low[u] > DFN[v]) {
Low[u] = DFN[v];
}
}
if (Low[u] == DFN[u]) {
block++;
do {
v = Stack[--top];
Instack[v] = false;
Belong[v] = block;
} while ( v != u );
}
}
void init()
{
tot = 0;
memset(head, -1, sizeof(head));
}
vector<int>vec[MAXN];
// 调用lca求最近公共祖先
// ans为在U和V之间加再加一个边，剩下的桥数量。
// int ans = 0;
int ans = 0;
int dist[MAXN];
int id;
int num = -1;
void dfs(int x, int pre)
{
dist[x] = dist[pre] + 1;
for (auto y : vec[x]) {
if (y != pre) {
dfs(y, x);
}
}
}
void solve(int N)
{
memset(DFN, 0, sizeof(DFN));
memset(Instack, false, sizeof(Instack));
Index = top = block = 0;
Tarjan(1, 1);
for (int i = 1; i <= block; i++) {
vec[i].clear();
}
for (int u = 1; u <= N; u++)
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (Belong[u] != Belong[v]) {
vec[Belong[u]].push_back(Belong[v]);
}
// vec[Belong[v]].push_back(Belong[u]);
}
// repd(i, 1, block) {
// sort(ALL(vec[i]));
// vec[i].erase(unique(ALL(vec[i])), vec[i].end());
// }
dfs(1, 0);
repd(i, 1, block) {
if (dist[i] > num) {
num = dist[i];
id = i;
}
}
dfs(id, 0);
repd(i, 1, block) {
ans = max(ans, dist[i]);
}
printf("%d\n", ans - 1);
}
int n, m;
int main()
{
//freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);
//freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);
init();
gg(n);
gg(m);
repd(i, 1, m) {
int x, y;
gg(x); gg(y);
addedge(x, y);
addedge(y, x);
}
solve(n);
return 0;
}
inline void getInt(int *p)
{
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '0');
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 - ch + '0';
}
} else {
*p = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 + ch - '0';
}
}
}
最新文章
- php解析json数组
- windows raid mode重新安装系统（win10）
- php截取字符串中的关键字，并高亮显示
- leetcode题解||Reverse Integer 问题
- Linux下安装Perl和Perl的DBI模块
- Sql Server 2008 卸载重新安装失败的解决办法！（多次偿试，方法均有效！）
- Hbase Region Server 启动失败
- OpenSSL MD5 API
- [亲测]七步学会ASP.NET Core 2.0怎么发布/部署到Ubuntu Linux服务器并配置Nginx反向代理实现域名访问
- openwrt MT7628 编译前更改为DHCP，root 密码、ssid、时区、主机名
- 第85节：Java中的JavaScript
- 自动生成实体类和xml
- 第二章 Java内存区域与内存溢出异常
- layui实现复选框全选，反选
- bzoj1008
- Windows 本地文件搜索神器
- 冲刺One之站立会议7 /2015-5-20
- ios项目开发（天气预报项目）：使用正则获取 weather.com.cn站点信息
- JMeter学习笔记--使用HTTP信息头管理器
- html中如何让table显示的更好