P2341 受欢迎的牛

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶

牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜

欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你

算出有多少头奶牛可以当明星。

输入格式

第一行：两个用空格分开的整数：N和M

第二行到第M + 1行：每行两个用空格分开的整数：A和B，表示A喜欢B

输出格式

第一行：单独一个整数，表示明星奶牛的数量

解决问题

显然,"喜欢"是单向的,具有传递性的.因此我们把奶牛和奶牛之间的"喜欢"抽象成有向图中的边,而每一只奶牛都是点.这个有向图并不能保证没有环,也就是说,可能出现一圈奶牛相互喜欢,那么他们在这个小群体里就都是明星.这个小群体,叫做强连通分量.所以我们通过tarjan将所有的强连通分量分别缩成点,同时记录一下这个点有多大,这样就省去了很多遍历的步骤.

如果一个强连通分量里有奶牛指向外面,那么这个强连通分量中的所有奶牛都喜欢这条边指向的奶牛.至于能够成为明星的强连通分量,那一定是所有分量都最终指向这个分量,且这个分量没有出边.然后这个分量里所有的奶牛就都是明星了.注意要记下每个强连通分量里有多少奶牛.

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#define N 10005
#define M 50005
using namespace std;

inline void read(int &x) {
    x = 0;
    char ch = getchar(), w = 0;
    while (!isdigit(ch)) w = (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    x = w ? -x : x;
    return;
}

int n, m, noe, chudu[N], ans, noz;
int to[M], next[M], head[N];
int noc, members[N], c[N];
int instack[N], stack[N], top, dfn[N], cnt, low[N];

inline void addedge(int from, int t) {
    to[++noe] = t;
    next[noe] = head[from];
    head[from] = noe;
    return;
}//加边

void tarjan(int now) {
    dfn[now] = ++cnt, low[now] = dfn[now], instack[now] = 1, stack[++top] = now;
    for (int i = head[now]; i; i = next[i]) {
       	if (!dfn[to[i]])
            tarjan(to[i]), low[now] = min(low[now], low[to[i]]);
        else
            if (instack[to[i]])
                low[now] = min(low[now], dfn[to[i]]);
    }
    if (low[now] == dfn[now]) {
        noc++;//发现了一个新的强连通分量
        while (stack[top] != now) {
            instack[stack[top]] = 0;
            c[stack[top]] = noc;//c[i]代表i所属的连通块的编号
            top--;
            members[noc]++;//记录这个新的强连通分量里有多少头奶牛
        }
        top--;
        instack[now] = 0;
        c[now] = noc;
        members[noc]++;//这里也不能忘了
    }
    return;
}

int main() {
	read(n), read(m);
	for (int i = 1, x, y; i <= m; ++i) {
		read(x), read(y);
		addedge(x, y);
	}
	for (int i = 1; i <= n; ++i)
		if (!dfn[i])
			tarjan(i);//常规操作tarjan
	for (int i = 1; i <= n; ++i)
		for (int j = head[i]; j; j = next[j])
			if (c[to[j]] != c[i])
				chudu[c[i]]++;//现在扫描所有点的出边,如果有指向不同的连通块的边就出度++.
	for (int i = 1; i <= noc; ++i) {
		if (chudu[i]) continue;//现在统计出度为0的强连通分量,此时每个强连通分量都视为一个点.
		ans += members[i];//统计牛数
		noz++;
	}
	if (noz > 1)//如果有多个出度为0的群组,显然两边均无法成为所有牛的明星.
		cout << 0 << endl;
	else
		cout << ans << endl;
	return 0;
}

欢迎批评和指正!