首页 > 其他分享 >【NOIP2015】【Vijos1979】信息传递(有向图最小环大小)

【NOIP2015】【Vijos1979】信息传递(有向图最小环大小)

时间:2023-02-08 11:38:22浏览次数:41  
标签:NOIP2015 有向图 Vijos1979 vis int ++ rG maxn book

problem

  • 给定一张n个点,n条边的有向图
  • 求图的最小环,输出大小

solution

kosaraju暴力求出所有强连通分量,取最小值即可

codes

//kosaraju
#include<iostream>
#include<algorithm>
#include<vector>
#define maxn 200010
using namespace std;
vector<int>G[maxn], rG[maxn];
vector<int>vs, cmp[maxn];
int vis[maxn], book[maxn], cnt;
void dfs(int u){
    if(vis[u])return ;
    vis[u] = 1;
    for(int i = 0; i < G[u].size(); i++)dfs(G[u][i]);
    //for(int i = 0; i < G[u].size(); i++)if(!vis[G[u][i]])dfs(G[u][i]);
    vs.push_back(u);
}
void rdfs(int u){
    //if(book[u])return ;
    book[u] = cnt;
    cmp[cnt].push_back(u);
    for(int i = 0; i < rG[u].size(); i++)if(!book[rG[u][i]])rdfs(rG[u][i]);
    //for(int i = 0; i < rG[u].size(); i++)rdfs(rG[u][i]);
}
int main(){
    int n;   cin>>n;
    for(int i = 1; i <= n; i++){
        int x;  cin>>x;
        G[i].push_back(x);
        rG[x].push_back(i);
    }
    for(int i = 1; i <= n; i++)dfs(i);
    for(int i = n-1; i >= 0; i--){
        if(!book[vs[i]]){
            ++cnt;
            rdfs(vs[i]);
        }
    }
    int ans = 0xffffff;
    for(int i = 1; i <= cnt; i++){
        int si = cmp[i].size();
        if(si != 0 && si != 1){
            ans = min(ans, si);
        }
    }
    cout<<ans<<"\n";
    return 0;
}

标签:NOIP2015,有向图,Vijos1979,vis,int,++,rG,maxn,book
From: https://blog.51cto.com/gwj1314/6043779

相关文章

  • 【NOIP2015】【Luogu2678】跳石头
    problemsolutioncodes//二分答案//QAQ注意:起点和终点也是有石头的w#include<iostream>#include<algorithm>#definemaxn100010usingnamespacestd;intll,n,......
  • tarjan求有向图强连通分量
    tarjan算法的简单应用hdu1269题目链接题意给定有向图,问改有向图是否只有一个强连通分量思路tarjan算法求有向图强连通分量的简单应用代码#include<iostream>......
  • Solution 题解 UVA1389 Hard Life: 最小割,有向图,分数规划,和牛顿迭代
    题解UVA1389HardLife:最小割,有向图,分数规划,和牛顿迭代Preface黑题好耶看到了题解里面大多数是二分,我就来讲一讲简单又快速的DinkelbachAlgorithm吧!0-1分数规划......
  • [NOIP2015 提高组] 子串 【计数dp】
    题面https://www.luogu.com.cn/problem/P2679分析CCF数据真的水。不过还是要写下正解:令\(dp[i][j][t][0/1]\)表示\(a\)串前\(i\)个字符,\(b\)串前\(j\)个字符,匹配子串数......
  • NC16466 [NOIP2015]信息传递
    题目链接题目题目描述有n个同学(编号为1到n)正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为i的同学的信息传递对象是编号为Ti的同......
  • 有向图的拓扑排序——DFS
    在有向图的拓扑排序——BFS这篇文章中,介绍了有向图的拓扑排序的定义以及使用广度优先搜索(BFS)对有向图进行拓扑排序的方法,这里再介绍另一种方法:深度优先搜索(DFS)。算法考虑......
  • 【数据结构】五分钟带你了解及自定义有向图
    前言什么是有向图在数学中,一个图(Graph)是表示物件与物件之间的关系的方法,是图论的基本研究对象。一个图看起来是由一些小圆点(称为顶点或结点)和连结这些圆点的直线或曲线(......
  • 洛谷 P2679 [NOIP2015 提高组]子串
    \(70pts\):记\(sub_A(i)\)表示\(A\)的前\(i\)个字符构成的子串,相应地,\(sub_B(i)\)为\(B\)的前\(i\)个字符构成的子串。设\(f(i,j,k)\)表示在\(sub_A(i......
  • 跳石头(NOIP2015)
    AcWing洛谷解题思路这题看到最短跳跃距离尽可能长就会想到二分但是我们二分的\(check\)函数怎么写呢可以看到限制条件移走的石头最多只能是\(m\)块我们二分这个最短......
  • 有向图最小环的三种普遍求法 Dijkstra
    有向图的最小环问题Dijkstra两点距离和跑\(n\)遍\(\text{Dijkstra}\)求出任意两点间距离,然后枚举任意两点\(i,j\),可以发现\(dist[i][j]+dist[j][i]\)就是一个可......