bzoj 1051: [HAOI2006]受欢迎的牛 tarjan缩点

2022-04-09 00:20:55

1051: [HAOI2006]受欢迎的牛

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2092 Solved: 1096
[Submit][Status]

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

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

突然发现以前的tarjan都时有问题的，vis标记应该出栈的时候打，而非退出是打。这道题缩点后判断“树根”本是非常简单的问题，然而由于思考不够深入，没有抓住"当且仅当DAG退化为“树”，才有解"的特性，所以编了半天还是错的。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define MAXN 11000

#define MAXV MAXN

#define MAXE MAXN*20

struct Edge

{

        int np;

        Edge *next;

}E[MAXE],*V[MAXV];

int tope=-;

void addedge(int x,int y)

{

        E[++tope].np=y;

        E[tope].next=V[x];

        V[x]=&E[tope];

}

int low[MAXN],dfn[MAXN];

int dfstime=;

int stack[MAXN];

int tops=-;

int color[MAXN],topc=;

int size_c[MAXN];

int size_sub[MAXN];

bool vis[MAXN];

set<int> S[MAXN];

void tarjan(int now)

{

        low[now]=dfn[now]=++dfstime;

        Edge *ne;

        stack[++tops]=now;

        for (ne=V[now];ne;ne=ne->next)

        {

                if (vis[ne->np])continue;

                if (dfn[ne->np])

                {

                        low[now]=min(low[now],dfn[ne->np]);

                }else

                {

                        tarjan(ne->np);

                        low[now]=min(low[now],low[ne->np]);

                }

        }

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

        {

                ++topc;

                while (stack[tops]!=now)

                {

                        vis[stack[tops]]=true;

                        color[stack[tops--]]=topc;

                        size_c[topc]++;

                }

                vis[stack[tops]]=true;

                color[stack[tops--]]=topc;

                size_c[topc]++;

        }

}

pair<int,int> edge[MAXE];

int topedge;

int degree[MAXN];

queue<int> Q;

int main()

{

        freopen("input.txt","r",stdin);

        int n,m;

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

        int i,j,k,x,y,z;

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

        {

                scanf("%d%d",&x,&y);

                addedge(x,y);

                edge[i].first=x;

                edge[i].second=y;

        }

        sort(edge,&edge[m]);

        topedge=;

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

        {

                if (edge[i]!=edge[topedge])

                        edge[++topedge]=edge[i];

        }

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

        {

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

        }

    //    memset(V,0,sizeof(V));

    //    tope=-1;

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

        {

                if (color[edge[i].first]==color[edge[i].second])continue;

        //        if (S[color[edge[i].first]].find(color[edge[i].second])!=S[color[edge[i].first]].end())continue;

    //            addedge(color[edge[i].first],color[edge[i].second]);

        //        S[color[edge[i].first]].insert(color[edge[i].second]);

                degree[color[edge[i].first]]++;

        }

        int ans;

        ans=;

        for (i=;i<=topc;i++)

        {

                if (degree[i]==)ans++,x=i;

        }

        if (ans==)

        {

                printf("%d\n",size_c[x]);

        }else

        {

                printf("0\n");

        }

        return ;

}

码农公寓