专栏首页calmound强联通模板

强联通模板

#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
using namespace std;
const int MN=2011;

vector<int>edge[MN];
vector<int>SCC[MN];
stack<int>s;

int low[MN],dfn[MN];
int instack[MN],stap[MN];
int belong[MN];
int num[MN];
int ind[MN];
int tp,p;
int bcnt;

void tarjan(int x)
{
    low[x]=dfn[x]=++tp;
    stap[++p]=x;
    instack[x]=1;
    for(int i=0;i<edge[x].size();i++)
    {
        int v=edge[x][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            if(low[x]>low[v])
               low[x]=low[v];
        }
        else if(instack[v] && dfn[v]<low[x])
               low[x]=dfn[v];
    }
    if(low[x]==dfn[x])
    {
        int top;
        do
        {
            top=stap[p];
            belong[top]=bcnt;//缩点
            instack[top]=0;
            p--;
        }while(x!=top);
        bcnt++;
    }
}

void topsort()//求入度
{
    memset(num,0,sizeof(num));
    int i,u,v;
    while(!s.empty())
        s.pop();
    for(int i=0;i<bcnt;i++)
        if(ind[i]==0)
        {
            s.push(i);
            num[i]++;
        }
    while(!s.empty())
    {
        u=s.top();
        s.pop();
        for(int i=0;i<SCC[u].size();i++)
        {
            v=SCC[u][i];
            if(--ind[v]==0)
            {
                s.push(v);
                num[v]=num[u]+1;
            }
        }
    }
}

int main()
{
    int T,n,m,i,a,b,j;
    scanf("%d",&T);
    while(T--)
    {
        bcnt=tp=p=0;
        scanf("%d%d",&n,&m);
        memset(dfn,-1,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(instack,0,sizeof(instack));
        memset(belong,0,sizeof(belong));
        memset(ind,0,sizeof(ind));
        for(i=1;i<=n;i++)
        {
            edge[i].clear();
            SCC[i].clear();
        }
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            edge[a].push_back(b);
        }
        for(i=1;i<=n;i++)
        {
            if(dfn[i]==-1) tarjan(i);
        }
        for(i=1;i<=n;i++)//缩点后建图
        {
            for(j=0;j<edge[i].size();j++)
            {
                int x=belong[i];
                int y=belong[edge[i][j]];
                if(x!=y)
                {
                     SCC[x].push_back(y);
                     ind[y]++;
                }
            }
        }
        topsort();
        int ans=-1;
        for(i=0;i<bcnt;i++)
        {
            ans=max(ans,num[i]);
        }
        if(bcnt==ans) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 强连通专题

    POJ 2762 Going from u to v or from v to u? 题意:判断该图的任意两点是否可达 分析:tarjan后进行缩点,缩点后再建...

    用户1624346
  • 强连通专题

    求割点(无向边): 所谓的割点,就是删除某个点,图便不连通了。  POJ  1523 #include<stdio.h> #include<string.h> ...

    用户1624346
  • Remove Duplicates from Sorted Array

    问题:将有序的数组中重复的数字去掉 分析:由于有序所以只用和前一个比较就行 class Solution { public: int removeDup...

    用户1624346
  • 强连通专题

    POJ 2762 Going from u to v or from v to u? 题意:判断该图的任意两点是否可达 分析:tarjan后进行缩点,缩点后再建...

    用户1624346
  • 「2017 Multi-University Training Contest 1」2017多校训练1

    饶文津
  • C++版 - 剑指offer面试题38:数字在已排序数组中出现的次数

    提交网址: http://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=13&...

    Enjoy233
  • NOI接水问题

    15:接水问题 总时间限制: 1000ms 内存限制: 65536kB 描述 学校里有一个水房,水房里一共装有 m 个龙头可供同学们打开水,每个龙头每秒钟...

    zy010101
  • BZOJ3004: 吊灯(结论 毒瘤)

    结论:若$k$是可行的,则至少有$\frac{n}{k}$个节点的大小为$k$的倍数

    attack
  • 1464: [蓝桥杯2019初赛]数的分解

    把2019分解成3个各不相同的正整数之和,并且要求每个正整数都不包含数字2和4,一共有多少种不同的分解方法?注意交换3个整数的顺序被视为同一种方法,例如1000...

    可爱见见
  • C++11新语法糖之尾置返回类型

    C++11的尾置返回类型初衷是为了方便复杂函数的声明和定义,但是当复杂度稍微提升一些的时候很明显能注意到这种设计的作用微乎其微.

    racaljk

扫码关注云+社区

领取腾讯云代金券