首页 > 其他分享 >P2860 [USACO06JAN]Redundant Paths G 题解 tarjan边双连通分量

P2860 [USACO06JAN]Redundant Paths G 题解 tarjan边双连通分量

时间:2023-06-17 10:05:35浏览次数:56  
标签:Paths tarjan int 题解 head ecnt edge low id

题目链接:https://www.luogu.com.cn/problem/P2860

题目大意:

给定一个无向连通图,求至少加几条边,能使其变成一个边双连通图。

解题思路:

边双连通分量缩点后计算度数为 \(1\) 的节点个数,假设有 \(cnt\) 个,则答案为 \((cnt+1)/2\)。

示例程序:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5050, maxm = 20020;
struct Edge {
    int u, v, nxt;
} edge[maxm];
int n, m, head[maxn], ecnt;

void init() {
    memset(head, -1, sizeof(int)*(n+1));
    ecnt = 0;
}

void addedge(int u, int v) {
    edge[ecnt] = {u, v, head[u]}; head[u] = ecnt++;
    edge[ecnt] = {v, u, head[v]}; head[v] = ecnt++;
}

int dfn[maxn], low[maxn], id[maxn], ts, dcc;
bool vis[maxm];
stack<int> stk;

void tarjan(int u) {
    dfn[u] = low[u] = ++ts;
    stk.push(u);
    for (int i = head[u]; i != -1; i = edge[i].nxt) {
        if (vis[i]) continue;
        vis[i] = vis[i^1] = true;
        int v = edge[i].v;
        if (!dfn[v])
            tarjan(v), low[u] = min(low[u], low[v]);
        else
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        dcc++;
        int v;
        do {
            v = stk.top();
            stk.pop();
            id[v] = dcc;
        } while (u != v);
    }
}

int d[maxn];

int main() {
    scanf("%d%d", &n, &m);
    init();
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v);
    }
    tarjan(1);
    for (int i = 0; i < 2*m; i += 2) {
        int u = edge[i].u, v = edge[i].v;
        if (id[u] != id[v])
            d[id[u]]++, d[id[v]]++;
    }
    int cnt = 0;
    for (int i = 1; i <= dcc; i++) if (d[i] == 1) cnt++;
    printf("%d\n", (cnt + 1) / 2);
    return 0;
}



标签:Paths,tarjan,int,题解,head,ecnt,edge,low,id
From: https://blog.51cto.com/u_13536312/6504545

相关文章

  • 和与积 题解 简单二分查找
    题目大意:给定两个整数\(a(2\lea\le2\times10^9)\)和\(b(1\leb\le10^{18})\)。判断是否存在两个正整数\(x\)和\(y\),同时满足如下两个条件:\(x+y=a\)\(x\timesy=b\)解题思路:用\(a-x\)表示\(y\),可以得到面积的表达式为\(x\times(a-x)\),然后可以发现......
  • CF402E Strictly Positive Matrix 题解 tarjan强连通分量
    题目链接:http://codeforces.com/problemset/problem/402/E题目大意:给出一个矩阵\(A\),问是否存在一个正整数\(k\)使得\(A^k\)解题思路:根据矩阵的性质,\(A^k_{i,j}\gt0\)当且仅当\(i\)到\(j\)所以可以把矩阵转成图论模型,若\(A_{i,j}\gt0\),则从\(i\)往\(j\)如果所有点......
  • NOIP2020 T2 字符串匹配【题解】
    NOIP2020T2字符串匹配首先声明这篇题解存在大多数让我这种人看懂的废话,如果想要速通,请另寻他解题目简化定义字符串乘法为\(AB\)为把两个字符串拼起来,定义阶乘\(A^i\)表示\(\prod_{1}^iA\)再定义\(F(S)\)为\(S\)中出现奇数次字符的数量现给定一个字符串\(S\),求......
  • P1903 [国家集训队] 数颜色 / 维护队列 题解
    一、题目描述:给你一个长度为$n$的序列$a$,你需要进行$m$次操作。$类型\1\:将第\x\个元素的值修改为\v\。$$类型\2\:求区间\l\到\r\中有多少种数字。$数据范围:$1\len,m\le1333333,所有数字\le1\times10^6$ 二、解题思路:带......
  • CF1205C Palindromic Paths 题解
    很好的一道题,思路自然,步骤清晰,结论好猜。唯一的缺点可能只是我赛时没有看到。构造可行解看到题目,也许我们很快就能想出一个做法:每次询问\((i,j,i+1,j)\),每行第一个额外询问\((i,j,i+1,j)\),这样询问总共\(n^2-1\)次即可。当我们怀疑看错题目重新检查时发现了被微软翻译......
  • 「ULSG-1」泡水的铅筒 题解
    题目传送门题目描述一个圆锥放入一个长方体水池中,无水溢出,求长方体液面高度的最大、最小值。解题思路如果这个题只有一个数据点,此数据点只有一组数据,那这就是一道初中填空题()先考虑\(h1\)的最小值。由“铅筒被完全浸没且没有液体溢出水池外”一句可得,若圆锥放入水池后液面高......
  • 「ULSG-1」2048 题解
    题目传送门题目解析玩一次就明白了。传送门解题思路合并从下往上,从左往右,对于每一个非零的数,向上第一个非零数,若与之相等,则此数与找到的数相加,同时分数加上合并后的数,而找到的数清零。若第一个非零数与它不相等,直接停止寻找过程,意为无法合并,等待下落。下落依旧从下往上,从......
  • 「ULSG-1」数字生命 题解
    题目传送门题目描述给定一段长度为\(n\)的序列,找出其中长度为\(m\)的一段子序列,且其中各数字出现次数与给定模板中相对应的次数不相同的数字等于\(k\)。题目解法容易联想到一个用于求固定长度区间最大值的\(O(n)\)算法——「滑动窗口」,此题可借鉴此算法。我们以此题的......
  • 「SiR-1」Checkmate 题解
    题外话:本体题目出自番剧《NOGAMENOLIFE》且题目背景中来吧,游戏开始了。是第一季中男主“空”的口头禅。(强烈推荐观看《NOGAMENOLIFEZERO》)回归正题awaP9355「SiR-1」Checkmate题解题目传送门博客宣传题目解读:在\(n\)行\(m\)列的棋盘中放置多枚棋子,求出其上......
  • 【BZOJ 3156】防御准备 题解
    原题令\(S_{i}=\sum_{j=1}^{i}j\),\(f_{i}\)为处理到第\(i\)个位置放置守卫塔的最小花费。观察题意,容易得到在\((1<=j<=i-1)\)时,有\(f_{i}=min\left\{f_{j}+\sum_{k=j+1}^{i-1}(i-k)+a_{i}\right\}\)①\(f_{i}=min\left\{f_{j}+\sum_{k=j+1}^{i-1}(i-k)\ri......