题目链接:
题目: 给定一个连通图, 题目说, 任意两个点至少有一条路线可以相互到达,
为保证任意两点有完全不同的路线 (点可以相同, 边不能相同) 可以相互到达至少需要加几条边.
思路: tarjan 缩点, 之后重构图, 找出度数为 1 的 scc 个数 scc_cnt, 这些点相互连接, 答案可以得出是 (scc_cnt+1)/2.
两组样例:
- n = 5 ,m = 4 | (1 2) (1 3) )(1 4) (1 5)
- n = 8, m = 9 | (1 2) (1 4) (2 3) (3 4) (4 5) (5 6) (6 7) (5 8) (7 8 )
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- using namespace std;
- const int N = (int)5e3+10;
- int head[N],dfn[N],low[N],scc_no[N],s[N],du[N];
- int n,m,tot,tim,scc,top;
- struct node{
- int to;
- int nxt;
- }e[N <<2];
- inline void add(int u,int v){
- e[tot].to = v;
- e[tot].nxt = head[u];
- head[u] = tot++;
- }
- void tarjan(int now,int pre){
- dfn[now] = low[now] = ++tim;
- s[top++] = now;
- // 这里有情况, 两点之间可能 > 1 条路直接连接
- // 所以, 需要处理下边的重复问题
- int to,pre_cnt = 0;
- for(int o = head[now]; ~o; o = e[o].nxt){
- to = e[o].to;
- // 只是一条无向边, 处理一下
- if(to == pre && pre_cnt == 0){
- pre_cnt = 1;
- continue;
- }
- if(!dfn[to]){
- tarjan(to,now);
- low[now] = min(low[now],low[to]);
- }
- else low[now] = min(low[now],dfn[to]);
- }
- if(dfn[now] == low[now]){
- ++scc;
- int x;
- do{
- x = s[--top];
- scc_no[x] = scc;
- }while(now != x);
- }
- }
- void rebuild(){
- int to;
- for(int now = 1; now <= n; ++now){
- for(int o = head[now]; ~o; o = e[o].nxt){
- to = e[o].to;
- if(scc_no[now] != scc_no[to]){
- ++du[scc_no[now]];
- ++du[scc_no[to]];
- }
- }
- }
- }
- void solve(){
- int p = 0;
- // cout << scc << endl;
- // 度数为什么是 2 的, 因为是无向图, 其实除 2 就是度数为 1 了
- for(int i = 1; i <= scc; ++i)
- if(du[i] == 2) ++p;
- // cout << p << endl;
- printf("%d\n",(p+1)/2);
- }
- int main(){
- int u,v;
- scanf("%d%d",&n,&m);
- for(int i = 1;i <= n; ++i) head[i] = -1;
- for(int i = 0; i < m; ++i){
- scanf("%d%d",&u,&v);
- add(u,v); add(v,u);
- }
- tarjan(1,1);
- rebuild();
- solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3382721.html