首页 > 其他分享 >【模板】缩点

【模板】缩点

时间:2024-08-10 21:50:12浏览次数:14  
标签:缩点 __ head int scc low include 模板

\[\Large 给出一个图,求出SCC后缩点得到新的图 \]

做法:Tarjan 记录scc 然后根据SCC去重新建图

#include <cstdio>
#include <stack>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#define ep emplace_back 

#define lld long long 
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0); 
#define vec vector 
const int N = 4e5+9;

const int INF = 0x7FFFFFFF; //2147483647

const int inf1 = 0x3f3f3f3f; //1061109567
const int inf2 = 0x7f7f7f7f; //2139062143 memset赋值用

using namespace std;

int head[N], idx = 0;
bool vis[N];
struct node {
    int to, val, next;
};
node e[N];
int n, m;
int time_ = 0;
stack<int> st;
int low[N], dfn[N];
int scc[N], scc_cnt = 0;  // 用于标记强连通分量的总数,也是每个点的scc编号
int a[N], p[N], in[N];
lld ans = 0,dist[N]; // 新增:一些需要的变量
int din[N];
void add(int u, int v, int val) {
    e[idx] = {v, val, head[u]};
    head[u] = idx++;
}
node ee[N];
int idx__=0,head__[N];
void add__(int u,int v,int val){
    ee[idx__] = {v,val,head__[u] };
    head__[u] = idx__++;
}
void bd() {
    cin >> n >> m;
    memset(head, -1, sizeof(head));
    memset(head__, -1, sizeof(head__));
    //for (int i = 1; i <= n; ++i) cin >> a[i];
    //如果每个点有权值的话
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        add(u, v,0);
    }
}

void tarjan(int u) {
    low[u] = dfn[u] = ++time_;
    vis[u] = true;
    st.push(u);
    for (int i = head[u]; i != -1; i = e[i].next) {
        int v = e[i].to;
        if (dfn[v] == 0) {
            tarjan(v);
            low[u] = min(low[u], low[v]); // 修正:low[u] 应该和 low[v] 比较
        } else if (vis[v]) {
            //如果在stack中
            low[u] = min(low[u], dfn[v]);
            //low(u)和他字节点的时间戳比较
        }
    }

    if (low[u] == dfn[u]) {
        //每个scc的根节点
        ++scc_cnt;//scc编号
        while (true) {
            int v = st.top();
            st.pop();
            vis[v] = false;//出栈
            scc[v] = scc_cnt; // 给每个点分配一个 scc 编号
            p[scc_cnt] += a[v]; // 将权值累加到对应的 scc 上
            if (v == u) break;
        }
    }
}

void debug(){
    //检查tarjan后的scc值
    for(int i=1 ; i<=n ; ++i)
        cout<<scc[i]<<"\n";
    
}
void bd__() {
    for (int i = 1; i <= n; ++i) {
        for (int u = head[i]; u != -1; u = e[u].next) {  // 注意循环变量的使用
            int v = e[u].to;
            // 每个点对应的 SCC
            int scc_u = scc[i];  // 注意,这里应该是 i 对应的 SCC
            int scc_v = scc[v];
            if (scc_u != scc_v) {
                // 不在同一个 SCC 里面,而且 u 连接了 v,说明 scc_u 连接了 scc_v
                add__(scc_u, scc_v, 0);
                din[scc_v]++;
            }
        }
    }
}
int main() {
    ios;
    bd();
    for (int i = 1; i <= n; ++i)
        if (!dfn[i]) tarjan(i);
        //如果没有访问过 那么就访问  否则跳过  time:O(n+m)
    bd__();

    return 0;
}

标签:缩点,__,head,int,scc,low,include,模板
From: https://www.cnblogs.com/Phrink734/p/18352829

相关文章

  • 011.Vue3入门,计算属性的使用,让模板语法更简洁
    1、代码如下:<template><h3>计算属性</h3><div>{{func1}}</div><div>{{func1}}</div><div>{{func1}}</div><!--<div>{{func1()}}</div>--><!--<div>{{func1()}}&......
  • 002.Vue3入门,使用模板语法的一些高级功能
    1、代码如下:<template><h3>模板语法</h3><p>{{msg}}</p><p>{{msg_cn}}</p><p>{{number+1}}</p><p>{{ok?'Yes':'No'}}</p><p>{{message.split("......
  • P3834 【模板】可持久化线段树 2
    原题链接题解总体上来讲,就是二分\(x\)查询插入\(l-1\)时有多少数小于等于\(x\),查询插入\(r\)时有多少数小于等于\(x\)然后减一减,看看是不是小于等于\(k-1\)我认为目前没有比ai讲的更清楚的了,请点击这里code#include<bits/stdc++.h>usingnamespacestd;/*#def......
  • 【数据结构】【模板】哈夫曼树
    哈夫曼树定义带权路径长度:结点的权值乘以结点到跟的距离。树上所有结点带权路径长度之和最小的二叉树称为哈夫曼树。性质哈夫曼是满二叉树。来自维基百科:原序列构成哈夫曼树的所有叶子结点。离根结点越近,点权越大。非叶子结点的点权之和就是所有叶子结点的带权路径之和......
  • 网页设计模板范例
    随着互联网的发展,网页设计变得越来越重要。一个吸引人的网页设计可以吸引更多的用户,提升用户体验,并且使网站内容更加易于浏览和理解。在这篇文章中,我将为大家介绍一个网页设计模板范例。1.选择合适的颜色和字体:一个好的网页设计应该有一个统一的颜色和字体方案。首先,选择主......
  • Meissel_Lehmer模板
    复杂度\(O(n^\frac23)\),计算\(1\simn\)的素数个数#definediv(a,b)(1.0*(a)/(b))#definehalf(x)(((x)-1)/2)i64Meissel_Lehmer(i64n){if(n<=3){returnmax(n-1,0LL);}longlongv=sqrtl(n);ints=(v+1)/2......
  • 模板 - 二分&三分
    二分&三分整数二分intBinarySearch(constintL,constintR){ intl=L-1,r=R+1; while(l+1<r) { intmid=l+r>>1; if(check(mid))l=mid; elser=mid; } returnl;}浮点数二分constdoubleEPS=1e-6;doubleBinarySearch(constdoubleL,constdouble......
  • 模板 - 数据结构
    链表定义structPeter{ intval; intnxt,pre;}node[M];intidx=0;初始化inlinevoidInit()//head:0;tail:n+1{ node[0]={0,n+1,0}; node[n+1]={0,n+1,0}; return;}在p后插入valinlinevoidinsert(intp,intval){ node[++idx]={val,node[p].nxt,p}; ......
  • 【C++】模板(相关知识点讲解 + STL底层涉及的模板应用)
    目录模板是什么?模板格式模板本质函数模板格式介绍显式实例化模板参数匹配原则类模板类模板的实例化非类型模板参数模板特化——概念函数模板特化类模板的特化全特化半特化偏特化三种类特化例子(放一起比较)模板分离编译STL中比较经典的模板应用(不包含argus)......
  • 移情别恋c++ ദ്ദി˶ー̀֊ー́ ) ——4.模板
    1.泛型编程如何实现一个通用的交换函数呢?voidSwap(int&left,int&right){inttemp=left;left=right;right=temp;}voidSwap(double&left,double&right){doubletemp=left;left=right;right=temp;}voidSwap(char&left,char&right)......