「BZOJ1051」[HAOI2006] 受欢迎的牛

2014年1月8日10,3304

Description

每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。这种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。

Input

第一行两个数N,M。接下来M行，每行两个数A,B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可能出现多个A,B）

Output

一个数，即有多少头牛被所有的牛认为是受欢迎的。

Sample Input

3 3
1 2
2 1
2 3

Sample Output

1「数据范围」
10%的数据N<=20, M<=50
30%的数据N<=1000,M<=20000
70%的数据N<=5000,M<=50000
100%的数据N<=10000,M<=50000

代码

tarjan强连通分量求缩点重构图，出度为0的点若只有一个则输出其代表强连通分量的大小，否则无解。

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m, ind, top, scc, ans;
int dfn[10005], low[10005], inq[10005], q[10005], bl[10005], size[10005], d[10005];
int u[50005], v[50005];
vector<int> e[10005];
void tarjan(int x)
{
    dfn[x] = low[x] = ++ind;
    q[++top] = x;
    inq[x] = 1;
    for(int i = 0; i < e[x].size(); i++)
        if(!dfn[e[x][i]])
        {
            tarjan(e[x][i]);
            low[x] = min(low[x], low[e[x][i]]);
        }
        else if(inq[e[x][i]])
            low[x] = min(low[x], dfn[e[x][i]]);
    if(dfn[x] == low[x])
    {
        int now = -1; scc++;
        while(now != x)
        {
            now = q[top]; top--;
            inq[now] = 0;
            bl[now] = scc;
            size[scc]++;
        }
    }
}
int main()
{
    n = read(); m = read();
    for(int i = 1; i <= m; i++)
    {
        u[i] = read(), v[i] = read();
        e[v[i]].push_back(u[i]);
    }
    for(int i = 1; i <= n; i++)
        if(!dfn[i])
            tarjan(i);
    for(int i = 1; i <= m; i++)
        if(bl[u[i]] != bl[v[i]])
            d[bl[u[i]]]++;
    for(int i = 1; i <= scc; i++)
    {
        if(d[i] == 0)
        {
            if(ans)
            {
                ans = 0;
                break;
            }
            ans = size[i];            
        }
    }
    printf("%d\n", ans);
    return 0;
}

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n, m, ind, top, scc, ans;

int dfn[10005], low[10005], inq[10005], q[10005], bl[10005], size[10005], d[10005];

int u[50005], v[50005];

vector<int> e[10005];

void tarjan(int x)

{

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

q[++top] = x;

inq[x] = 1;

for(int i = 0; i < e[x].size(); i++)

if(!dfn[e[x][i]])

{

tarjan(e[x][i]);

low[x] = min(low[x], low[e[x][i]]);

}

else if(inq[e[x][i]])

low[x] = min(low[x], dfn[e[x][i]]);

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

{

int now = -1; scc++;

while(now != x)

{

now = q[top]; top--;

inq[now] = 0;

bl[now] = scc;

size[scc]++;

}

int main()

{

n = read(); m = read();

for(int i = 1; i <= m; i++)

{

u[i] = read(), v[i] = read();

e[v[i]].push_back(u[i]);

}

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

if(!dfn[i])

tarjan(i);

for(int i = 1; i <= m; i++)

if(bl[u[i]] != bl[v[i]])

d[bl[u[i]]]++;

for(int i = 1; i <= scc; i++)

{

if(d[i] == 0)

{

if(ans)

{

ans = 0;

break;

}

ans = size[i];

}

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

return 0;

}

「CODEVS2822」爱在心中 »

qgz

黄学长，我有个问题求教：您打问号的那个地方，第27行，为什么要用dfn[e .to]而不用low[e .to]……

hzwer

你可以阅读一下https://www.byvoid.com/blog/scc-tarjan

X!!

黄学长，有一点不是很明白，这道题缩点的时候用的是++hav[scc]，这样假如出现了一个强联通分量被包含在另一个里面，hav的值不是会错？

hzwer

强连通分量为什么会有包含关系。。。是极大连通子图啊0.0

hzwer.com _ Home | http://hzwer.com

「BZOJ1051」[HAOI2006] 受欢迎的牛

Description

Input

Output

Sample Input

Sample Output

代码

分类目录

热门文章

Myfriends

近期评论