2186:Popular Cows--tarjan+缩点

题目大意

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 A 喜欢 B，B 喜欢 C，那么 A 也喜欢 C。牛栏里共有 N 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。

思路分析

先依次介绍tarjan算法求连通分量，和缩点的方法，然后给出AC代码

一、tarjan求强连通分量

1：算法流程

引用来自度娘的一句话：

“有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。”

反正就是在图中找到一个最大的图，使这个图中每个两点都能够互相到达。这个最大的图称为强连通分量，同时一个点也属于强连通分量。

tarjan算法，之所以用DFS就是因为它将每一个强连通分量作为搜索树上的一个子树。而这个图，就是一个完整的搜索树。

为了使这颗搜索树在遇到强连通分量的节点的时候能顺利进行。每个点都有两个参数。
1，DFN［］作为这个点搜索的次序编号（时间戳），简单来说就是 第几个被搜索到的。％每个点的时间戳都不一样％。

2，LOW［］作为每个点在这颗树中的，最小的子树的根，每次保证最小，like它的父亲结点的时间戳这种感觉。如果它自己的LOW［］最小，那这个点就应该从新分配，变成这个强连通分量子树的根节点。

ps：每次找到一个新点，这个点LOW［］＝DFN［］。

而为了存储整个强连通分量，这里挑选的容器是，堆栈（栈中所有点一定是有父子关系的）。每次一个新节点出现，就进站，如果这个点有 出度 就继续往下找。直到找到底，每次返回上来都看一看子节点与这个节点的LOW值，谁小就取谁，保证最小的子树根。如果找到DFN［］＝＝LOW［］就说明这个节点是这个强连通分量的根节点（毕竟这个LOW［］值是这个强连通分量里最小的。）最后找到强连通分量的节点后，就将这个栈里，比此节点后进来的节点全部出栈，它们就组成一个全新的强连通分量。

2：模板

#define MAX 10005
#define ll long long

vector<ll> g[MAX];
ll color[MAX], vis[MAX], stack[MAX], dfn[MAX], low[MAX], cnt[MAX];
//deep:节点编号 top：栈顶  sum：强连通分量数目
ll deep, top, sum, res = 0;

void tanjan(ll v) {
	dfn[v] = ++deep;
	low[v] = deep;   //(1)初始化dfn数组，同时将low设置为相同值
	vis[v] = 1;
	stack[++top] = v;//(2)入栈，作为栈顶元素，同时更新vis数组

	for (unsigned i = 0; i < g[v].size(); i++) {//(3)遍历所有可能到达的点
		ll id = g[v][i];
		if (!dfn[id]) {//如果这个点从没访问过，则先放问它，再用它更新low[v]的值
			tanjan(id);
			low[v] = min(low[v], low[id]); //他的儿子如果能连到更小的祖先节点，显然他也可以
		}
		else {
			if (vis[id]) {//不在栈中的点，要么没有访问，要么不能到达id，所以只需要判断栈中的
				low[v] = min(low[v], low[id]);
			}
		}
	}

	if (low[v] == dfn[v]) {//(4)自己和子节点形成了强连通分量，或者只有自己孤身一人
		color[v] = ++sum;
		vis[v] = 0;
		while (stack[top] != v) {//将从v开始所有的点取出
			color[stack[top]] = sum;//给予同一颜色
			vis[stack[top--]] = 0;//出栈要顺便修改vis
		}
		top--;
	}
}

二、tarjan缩点

1：相关定义

其实这也是利用了tarjan求强连通分量的方法，对于一些贡献具有传导性，比如友情啊、路径上的权值啊等等非常适用。

思想就是因为强连通分量中的每两个点都是强连通的，可以将一个强连通分量当做一个超级点，而点权按题意来定。

首先我们先看一下一个问题：一个有向图，有n个点以及m条边，我们至少应该添加几条边才能使整个图变成强连通图。或者是一个无向图至少添加几条边变成连通图。

首先我们对于一个有向无环的图（DAG），至少添加几条边才能使它变为强连通图？我们很容易根据有向无环图的性质得到，我们计算入度为零的点数为a，出度为零的点数为b，那么我们至少需要添加的边数为max(a,b)，如果只有一个点的话，我们不需要添加任何边。

那么我们怎么把一个图转换为DAG呢，因为上面给出的图可能存在环，那么我们就会想到把已经组成全连通的子图转换成一个点来看，那么我们最终的图就不会包含环了。

好了，解决这类问题的思路已经想好了，下面我们来进行求解：

我们使用Tarjan算法求解出强连通分量之后，我们上面使用了一个color数组将同一个连通分量的点分配相同的数值，然后我们再次遍历一遍所有的边，如果边的两侧u->v不属于同一颜色，那么u对应颜色将会有一条边连向v对应的颜色。在此基础上我们可以计算缩点之后的出入度，得到max(a,b)或者其他一些信息。

2：算法流程

其实我们上述的tarjan算法已经求出了每个点属于的color,其实每个color就代表了一个最大联通集，

#define MAX 10005
#define ll long long

vector<ll> g[MAX];
ll color[MAX], vis[MAX], stack[MAX], dfn[MAX], low[MAX], cnt[MAX], num[MAX];
ll ind[MAX], outd[MAX];//每个点的出度入度
//deep:节点编号 top：栈顶  sum：强连通分量数目
ll deep, top, sum, res = 0;

void tanjan(ll v) {
	dfn[v] = ++deep;
	low[v] = deep;   //(1)初始化dfn数组，同时将low设置为相同值
	vis[v] = 1;
	stack[++top] = v;//(2)入栈，作为栈顶元素，同时更新vis数组

	for (unsigned i = 0; i < g[v].size(); i++) {//(3)遍历所有可能到达的点
		ll id = g[v][i];
		if (!dfn[id]) {//如果这个点从没访问过，则先放问它，再用它更新low[v]的值
			tanjan(id);
			low[v] = min(low[v], low[id]); //他的儿子如果能连到更小的祖先节点，显然他也可以
		}
		else {
			if (vis[id]) {//不在栈中的点，要么没有访问，要么不能到达id，所以只需要判断栈中的
				low[v] = min(low[v], low[id]);
			}
		}
	}

	if (low[v] == dfn[v]) {//(4)自己和子节点形成了强连通分量，或者只有自己孤身一人
		color[v] = ++sum; num[sum]++; //num统计该颜色有多少点
		vis[v] = 0;
		while (stack[top] != v) {//将从v开始所有的点取出
			color[stack[top]] = sum;//给予同一颜色
			vis[stack[top--]] = 0;//出栈要顺便修改vis
			num[sum]++;
		}
		top--;
	}
}
int main(){
	for (int i = 1; i <= N; i++) {
		for (unsigned k = 0; k < g[i].size(); k++) {
			ll v = g[i][k];
			if (color[v] != color[i]) {//二者分属于不同的联通集
				outd[color[i]] += 1; //以颜色作为点，更新相应点的出度
			}
		}
	}
}

AC代码

#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<vector>
#include<cmath>
using namespace std;

#define MAX 10005
#define ll long long

vector<ll> g[MAX];
ll color[MAX], vis[MAX], stack[MAX], dfn[MAX], low[MAX], cnt[MAX], num[MAX];
ll ind[MAX], outd[MAX];//每个点的出度入度
//deep:节点编号 top：栈顶  sum：强连通分量数目
ll deep, top, sum, res = 0;

void tanjan(ll v) {
	dfn[v] = ++deep;
	low[v] = deep;   //(1)初始化dfn数组，同时将low设置为相同值
	vis[v] = 1;
	stack[++top] = v;//(2)入栈，作为栈顶元素，同时更新vis数组

	for (unsigned i = 0; i < g[v].size(); i++) {//(3)遍历所有可能到达的点
		ll id = g[v][i];
		if (!dfn[id]) {//如果这个点从没访问过，则先放问它，再用它更新low[v]的值
			tanjan(id);
			low[v] = min(low[v], low[id]); //他的儿子如果能连到更小的祖先节点，显然他也可以
		}
		else {
			if (vis[id]) {//不在栈中的点，要么没有访问，要么不能到达id，所以只需要判断栈中的
				low[v] = min(low[v], low[id]);
			}
		}
	}

	if (low[v] == dfn[v]) {//(4)自己和子节点形成了强连通分量，或者只有自己孤身一人
		color[v] = ++sum; num[sum]++; //num统计该颜色有多少点
		vis[v] = 0;
		while (stack[top] != v) {//将从v开始所有的点取出
			color[stack[top]] = sum;//给予同一颜色
			vis[stack[top--]] = 0;//出栈要顺便修改vis
			num[sum]++;
		}
		top--;
	}
}

int main() {
	ll N, M, a, b;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		g[a].push_back(b);
	}
	for (int i = 1; i <= N; i++) {
		if (!dfn[i]) //图可能是不连通的，因此依次tanjan算法可能不够，我们需要每个点判断一下
			tanjan(i);
	}

	for (int i = 1; i <= N; i++) {
		for (unsigned k = 0; k < g[i].size(); k++) {
			ll v = g[i][k];
			if (color[v] != color[i]) {//二者分属于不同的联通集
				outd[color[i]] += 1; //以颜色作为点，更新相应点的出度
			}
		}
	}
	
	for (int i = 1; i <= sum; i++) {
		if (!outd[i]) {//出度为0的点有了
			if (res > 0)
			{
				cout << 0 << endl; //超过两个出度为0的点
				return 0;
			}
			res = num[i];
		}
	}
	cout << res << endl;
}