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

题目链接：http://www.lydsy.com:808/JudgeOnline/problem.php?id=1051

题解：缩点之后判断出度为0的有几个，只有一个那么输出那个强连通块的点数，否者就输出0

#include <iostream>

#include <cstring>

#include <cstdio>

#include <map>

using namespace std;

const int N = 1e6 + 10;

const int M = 5e6 + 10;

map<int,int>mmp[N];

struct TnT {

    int v, next;

}edge[M];

int head[N], e;

int Low[N], DFN[N], Stack[N], Belong[N], num[N];

int Index, top, scc;

int Out[N];

bool Instack[N];

void init() {

    memset(head, -1, sizeof(head));

    e = 0;

}

void add(int u, int v) {

    edge[e].v = v;

    edge[e].next = head[u];

    head[u] = e++;

}

void Tarjan(int u) {

    int v;

    Low[u] = DFN[u] = ++Index;

    Stack[top++] = u;

    Instack[u] = true;

    for(int i = head[u]; i != -1; i = edge[i].next) {

        v = edge[i].v;

        if(!DFN[v]) {

            Tarjan(v);

            Low[u] = min(Low[u] , Low[v]);

        } else if(Instack[v]) Low[u] = min(Low[u] , DFN[v]);

    }

    if(DFN[u] == Low[u]) {

        scc++;

        do {

            v = Stack[--top];

            Instack[v] = false;

            Belong[v] = scc;

            num[scc]++;

        } while(v != u);

    }

}

int main() {

    int n, m;

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

    init();

    for(int i = 0; i < m; i++) {

        int a, b;

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

        if(mmp[a][b] != 1) {

            mmp[a][b] = 1;

            add(a , b);

        }

    }

    memset(DFN, 0, sizeof(DFN));

    memset(Low, 0, sizeof(Low));

    memset(Instack, false, sizeof(Instack));

    memset(num, 0, sizeof(num));

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

        if(!DFN[i]) Tarjan(i);

    }

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

        for(int j = head[i]; j != -1; j = edge[j].next) {

            int v = edge[j].v;

            if(Belong[i] != Belong[v]) Out[Belong[i]]++;

        }

    }

    int ans = 0 , pos = -1;

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

        if(Out[i] == 0) {ans++, pos = i;}

    }

    if(ans > 1) printf("0\n");

    else printf("%d\n" , num[pos]);

    return 0;

}

巴特西

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

最新文章

热门文章