洛谷 P2002 消息扩散

题目背景

本场比赛第一题，给个简单的吧，这 100 分先拿着。

题目描述

有n个城市，中间有单向道路连接，消息会沿着道路扩散，现在给出n个城市及其之间的道路，问至少需要在几个城市发布消息才能让这所有n个城市都得到消息。

输入输出格式

输入格式：

第一行两个整数n,m表示n个城市，m条单向道路。

以下m行，每行两个整数b,e表示有一条从b到e的道路，道路可以重复或存在自环。

输出格式：

一行一个整数，表示至少要在几个城市中发布消息。

输入输出样例

输入样例#1：

输出样例#1：

说明

【数据范围】

对于20%的数据，n≤200;

对于40%的数据，n≤2,000;

对于100%的数据，n≤100,000，m≤500,000.

【限制】

时间限制：1s，内存限制：256M

【注释】

样例中在4,5号城市中发布消息。

求入度为0的强连通分量

吐槽：说好的自环呢。。

屠龙宝刀点击就送

#include <cstdio>

#include <map>

#define N 500005

using namespace std;

map<pair<int,int>,bool>q;

int nextt[N],to[N],head[N],cnt,n,m,col[N],sumcol,low[N],dfn[N],tim,stack[N],top,rd[N];

bool instack[N];

inline void ins(int u,int v)

{

    nextt[++cnt]=head[u];

    to[cnt]=v;

    head[u]=cnt;

}

template<typename T>

inline T Min(T a,T b) {return a>b?b:a;}

void tarjan(int x)

{

    low[x]=dfn[x]=++tim;

    stack[++top]=x;

    instack[x]=true;

    for(int i=head[x];i;i=nextt[i])

    {

        int v=to[i];

        if(!dfn[v])

        {

            tarjan(v);

            low[x]=Min(low[x],low[v]);

        }

        else if(instack[v]) low[x]=Min(low[x],dfn[v]);

    }

    if(low[x]==dfn[x])

    {

        int k;

        sumcol++;

        do

        {

            k=stack[top--];

            col[k]=sumcol;

            instack[k]=false;

        }while(k!=x);

    }

}

int Main()

{

    scanf("%d%d",&n,&m);

    for(int a,b;m--;)

    {

        scanf("%d%d",&a,&b);

        if(a==b) continue;

        ins(a,b);

    }

    int sum=;

    for(int i=;i<=n;++i)

     if(!dfn[i]) tarjan(i);

    for(int i=;i<=n;++i)

     for(int j=head[i];j;j=nextt[j])

      if(col[i]!=col[to[j]])

       rd[col[to[j]]]++;

    for(int i=;i<=sumcol;++i) if(!rd[i]) sum++;

    printf("%d\n",sum);

    return ;

}

int sb=Main();

int main(int argc,char *argv[]){;}

巴特西

洛谷 P2002 消息扩散

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章