图论综合题

发表于2021-10-12更新于2021-10-12阅读次数

graph n个点 m条边

一般

K. Königsberg Bridges

题面：给一个n<1e6个点，m<1e6条边，添加几条边使得图存在一条路径遍历所有的桥，问桥最多能有多少条。

点击查看思路 
  


e-dcc+树的直径
注意图的坑点，是要存在一条路径遍历所有的桥，所以对于一棵树，使其桥最多的路，为直径。


  

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/*
* @Author: Marhoosh
* @Date:   2021-07-22 10:27:29
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-10-04 14:29:13
*/
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=1e6+11;
struct Edge{
    ll fr,to,next;
}edge[maxn<<1],edgesk[maxn<<1];
ll head[maxn],headsk[maxn],dfn[maxn],low[maxn],c[maxn],vis[maxn],d[maxn],ds[maxn];
ll dcc,tmp,tmpsk,cnt,n,m,num,zj;
bool bridge[maxn<<1];
void add(ll u,ll v){
    edge[tmp]={u,v};edge[tmp].next=head[u];
    head[u]=tmp++;
}
void addsk(ll u,ll v){
    edgesk[tmpsk]={u,v};edgesk[tmpsk].next=headsk[u];
    headsk[u]=tmpsk++;
}
void tarjan(ll x,ll faedge){
    dfn[x]=low[x]=cnt++;
    for(ll i=head[x];i;i=edge[i].next){
        ll y=edge[i].to;
        if(!dfn[y]){
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<low[y]){
                bridge[i]=bridge[i^1]=true;
            }
        }
        else if(i != (faedge ^ 1)){
            low[x]=min(low[x],dfn[y]);
        }
    }
}
void dfs(ll x){
    c[x]=dcc;
    for(ll i=head[x];i;i=edge[i].next){
        ll y=edge[i].to;
        if(c[y] || bridge[i])  continue;
        dfs(y);
    }
}
void dfsf(ll x,ll fa){
    vis[x]=1;
    if(d[x]>zj){
        zj=d[x];num=x;
    }
    for(ll i=headsk[x];i;i=edgesk[i].next){
        ll y=edgesk[i].to;
        if(y==fa)  continue;
        d[y]=d[x]+1;
        dfsf(y,x);
    }
}
void dfss(ll x,ll fa){
    vis[x]=1;
    if(ds[x]>zj){
        zj=ds[x];num=x;
    }
    for(ll i=headsk[x];i;i=edgesk[i].next){
        ll y=edgesk[i].to;
        if(y==fa)  continue;
        ds[y]=ds[x]+1;
        dfss(y,x);
    }
}
void solve(){
    ll ans=0;
    for(ll i=1;i<dcc;i++){
        if(!vis[i]){
            ans++;
            zj=-1;
            dfsf(i,-1);
            dfss(num,-1);
            ans+=zj;
        }
    }
    cout<<ans-1<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    tmp=tmpsk=2;cnt=1;dcc=1;
    for (ll i = 1; i <= m; i++) {
        ll x, y;cin>>x>>y;
        add(x, y), add(y, x);
    }
    for (ll i = 0; i < n; i++)
        if (!dfn[i]) tarjan(i, 0);
    for(ll i=0;i<n;i++){
        if(!c[i]){
            dfs(i);
            dcc++;
        }
    }
    for(ll i=2;i<tmp;i++){
        ll u=edge[i].fr,v=edge[i].to;
        if(c[u]==c[v])  continue;
        addsk(c[u],c[v]); //无向图
    }
    solve();
    return 0;
}