首页 > 其他分享 >Codeforces Round #286 (Div. 1) B. Mr. Kitayuta's Technology (强连通分量)

Codeforces Round #286 (Div. 1) B. Mr. Kitayuta's Technology (强连通分量)

时间:2023-04-13 22:37:08浏览次数:43  
标签:const int 连通环 Codeforces edge MAXN Mr include Round


题目地址:http://codeforces.com/contest/506/problem/B
先用强连通判环,然后转化成无向图,找无向图连通块,若一个有n个点的块内有强连通环,那么需要n条边,即正好首尾相连形成一条环,那么有了这个环之后,在这个块内的所有要求都能实现。如果没有强连通环,那么就是一棵树,那么只需要n-1条边即可。
代码如下:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
#include <time.h>
using namespace std;
#define LL long long
#define pi acos(-1.0)
#pragma comment(linker, "/STACK:1024000000")
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
const int MAXN=100000+10;
int head[MAXN], cnt;
int dfn[MAXN], low[MAXN], scc, belong[MAXN], instk[MAXN], stk[MAXN], indx, tot[MAXN], top;
int vis[MAXN];
int flag, num;
struct node
{
        int u, v, next;
}edge[MAXN<<1];
void add(int u, int v)
{
        edge[cnt].u=u;
        edge[cnt].v=v;
        edge[cnt].next=head[u];
        head[u]=cnt++;
}
void init()
{
        memset(head,-1,sizeof(head));
        cnt=indx=top=0;
        memset(dfn,0,sizeof(dfn));
        memset(instk,0,sizeof(instk));
        memset(tot,0,sizeof(tot));
}
void tarjan(int u)
{
        dfn[u]=low[u]=++indx;
        stk[++top]=u;
        instk[u]=1;
        for(int i=head[u];i!=-1;i=edge[i].next){
                int v=edge[i].v;
                if(!dfn[v]){
                        tarjan(v);
                        low[u]=min(low[u],low[v]);
                }
                else if(instk[v]) low[u]=min(low[u],dfn[v]);
        }
        if(dfn[u]==low[u]){
                scc++;
                while(1){
                        int v=stk[top--];
                        belong[v]=scc;
                        instk[v]=0;
                        tot[scc]++;
                        if(u==v) break;
                }
        }
}
void dfs(int u)
{
        num++;
        vis[u]=1;
        if(tot[belong[u]]>=2) flag=1;
        for(int i=head[u];i!=-1;i=edge[i].next){
                int v=edge[i].v;
                if(vis[v]) continue ;
                dfs(v);
        }
}
int main()
{
        int n, m, u, v, i, j, ans;
        while(scanf("%d%d",&n,&m)!=EOF){
                init();
                while(m--){
                        scanf("%d%d",&u,&v);
                        add(u,v);
                }
                ans=0;
                for(i=1;i<=n;i++){
                        if(!dfn[i])
                                tarjan(i);
                }
                m=cnt;
                for(i=0;i<m;i++){
                        u=edge[i].u;
                        v=edge[i].v;
                        add(v,u);
                }
                memset(vis,0,sizeof(vis));
                ans=0;
                for(i=1;i<=n;i++){
                        if(!vis[i]){
                                num=flag=0;
                                dfs(i);
                                ans+=num-1+flag;
                        }
                }
                printf("%d\n",ans);
        }
        return 0;
}


标签:const,int,连通环,Codeforces,edge,MAXN,Mr,include,Round
From: https://blog.51cto.com/u_16070138/6188452

相关文章

  • Codeforces Round #307 (Div. 2) E. GukiZ and GukiZiana (分块)
    题目地址:http://codeforces.com/contest/551/problem/E将n平均分成sqrt(n)块,对每一块从小到大排序,并设置一个整体偏移量。修改操作:l~r区间内,对两端的块进行暴力处理,对中间的整体的块用整体偏移量标记增加了多少。时间复杂度:O(2*sqrt(n)+n/sqrt(n)).查询操作:对每一块二分,查找......
  • Codeforces Round #303 (Div. 2) E. Paths and Trees (最短路+变形最小生成树)
    题目地址:E.PathsandTrees模拟了一场CF,这场实在太水了。。边玩边做的。。最后半分钟交了一发E题。。不幸AK绝杀失败。。。。首先的思路肯定是先求最短路,把可能为最短路的边挑出来,然后第二步我本来写的是直接用无向图的最小生成树,于是绝杀失败。。。后来才发现这样是不行的。......
  • Codeforces Round #316 (Div. 2) D. Tree Requests (DFS序)
    题目地址:http://codeforces.com/contest/570/problem/D比赛的时候实在没想到DFS序,。。想到DFS序后,分别存起每个深度的所有节点的DFS序,处理出前缀异或和,然后二分找到两个端点,再异或一下,就求出了所求区间的异或和,由于偶数次的都被异或掉了,所以判断下奇数次数是否大于1即可。代码......
  • Codeforces Round #284 (Div. 1) C. Array and Operations (最大流)
    题目地址:http://codeforces.com/contest/498/problem/C分别分解出每个数字的质因子,然后第奇数个数字的质因子在左边集合,偶数个数字的质因子在右边集合,建立源点和汇点,然后根据每个数字含有的质因子的个数建边,跑一遍最大流即可。代码如下:#include<iostream>#include<string.h>......
  • Codeforces Round #311 (Div. 2) E. Ann and Half-Palindrome (DP+字典树)
    题目地址:传送门先用dp求出所有的符合要求的半回文串,标记出来。然后构造字典树。然后再dfs一遍求出所有节点的子树和,最后搜一遍就能找出第k个来了。代码如下:#include<iostream>#include<string.h>#include<math.h>#include<queue>#include<algorithm>#include<stdlib......
  • Codeforces Round #Pi (Div. 2) E. President and Roads (最短路+强连通求割边)
    题目地址:codeforces#pi(DIV2)E题目很水。。就是先求两边最短路,然后把可能为最短路的边挑出来,然后判断是否yes只需要转化成无向图跑一遍tarjan,找出割边,割边就是yes,然后剩下的边就让它的值为最短路-1就行了,如果-1后变成了非正数,就是no.但是!!!居然卡spfa!!那是不是说cf以后就不......
  • Codeforces Round #305 (Div. 1) A.B.C 解题报告
    A.MikeandFrog枚举。先是找循环,然后很容易得出一个两元一次方程,然后可以发现解也是有循环节的,所以最小的那个肯定出现在一定范围内,否则就后面也不可能出现。假设两个变量为x,y,系数分别为z1,z2。很显然,两者的最小公倍数便是一个周期,所以如果枚举x的话,只需要枚举到z2就可......
  • codeforces#FF DIV2C题DZY Loves Sequences(DP)
    题目地址:http://codeforces.com/contest/447/problem/CC.DZYLovesSequencestimelimitpertestmemorylimitpertestinputoutputa,consistingof nai, ai + 1, .........
  • Codeforces Round #257 (Div. 1)B题Jzzhu and Cities(spfa+slf优化)
    题目地址:http://codeforces.com/contest/450/problem/D这题有重边,需要去重。。sad。当时居然没看见。。这题只要引入一个最短路条数,然后再遍历火车线,如果最短路与火车线长度相等,此时如果最短路条数是1的话,那说明这个最短路就是火车线,不能去掉,如果最短路条数大于1条,说明除了这条火车......
  • Educational Codeforces Round 146 (Rated for Div. 2)
    Preface补题ing值得一提的时补这场的时候先是遇上了CF的12小时大维护,后面又遇到了评测机崩了测不了也是有点有意思的说A.Coins傻逼题,首先考虑\(2|n\)时一定有解\(x=\frac{n}{2},y=0\),否则若\(2\nmidn\and2|k\)则由裴蜀定理知此时一定无解否则\(y\)必为奇数,我们令\(x=\fra......