受欢迎的牛 G

题目链接： / /

题目大意

有一个有向图，问你有多少个点可以从任意点出发都可以到达。

思路

首先，我们要找有多少点满足所有点都可以到它。

然后因为它不是无环图，我们会想到对于任何一个连通分量里面的每个点，它们之间都可以互相到达。

那我们可以把连通分量缩成一个点，那图就变成了 DAG，那在这个图上也就最多有一个点满足。

那怎么根据这个点看最终答案的数量呢？没错，其实就是这个点包含原来点的个数。

那怎么判断有没有那个点，以及那个点是哪个呢？

我们可以先想到，一定是找初度为

0

的点。

那如果多个点初度都是

0

，就肯定都不是。因为这两个点之间不能相互到达。

那找到这个点之后，我们可以再验证一下，反向建边，看从这个点跑反向建边的图能不能跑到所有点。（反向建边弄的是缩点后的图）

（不过好像是不用验证的，已近可以确定是可行的了）

代码

#include
   
    #include
    
     #include
     
      using namespace std;struct road {   	int x, y;}a[50001];struct node {   	int to, nxt;}e[50001], e_[50001], e_b[50001];int n, m, le[10001], KK, in[10001], n_;int dfn[10001], low[10001], st[10001], number;int num[10001], le_[10001], KK_, le_b[10001];int out[10001], ans, ans_num, KK_b;bool inn[10001];queue 
      
        q;bool cmp(road x, road y) {   //用来去重边的排序	if (x.x != y.x) return x.x < y.x;	return x.y < y.y;}void add(int x, int y) {   //初始图	e[++KK] = (node){   y, le[x]}; le[x] = KK;}void add_(int x, int y) {   //缩点后的图	e_[++KK_] = (node){   y, le_[x]}; le_[x] = KK_;}void add_b(int x, int y) {   //缩点后反向的图	e_b[++KK_b] = (node){   y, le_b[x]}; le_b[x] = KK_b;}void tarjan(int now) {   //Tarjan缩点	dfn[now] = low[now] = ++number;	st[++st[0]] = now;		for (int i = le[now]; i; i = e[i].nxt)		if (!dfn[e[i].to]) {   			tarjan(e[i].to);			low[now] = min(low[now], low[e[i].to]);		}		else if (!in[e[i].to]) low[now] = min(low[now], low[e[i].to]);		if (dfn[now] == low[now]) {   		in[now] = ++n_;		num[n_] = 1;		while (st[st[0]] != now) {   			in[st[st[0]]] = n_;			num[n_]++;			st[0]--;		}		st[0]--;	}		return ;}int dfs(int now) {   //跑dfs序看是否是可以全部点都到它	int re = 1;	inn[now] = 1;	for (int i = le_b[now]; i; i = e_b[i].nxt)		if (!inn[e_b[i].to])			re = re + dfs(e_b[i].to);	return re;}int main() {   	scanf("%d %d", &n, &m);	for (int i = 1; i <= m; i++) {   		scanf("%d %d", &a[i].x, &a[i].y);	}		sort(a + 1, a + m + 1, cmp);	add(a[1].x, a[1].y);	for (int i = 2; i <= m; i++)//去了重边再建图		if (a[i].x != a[i - 1].x || a[i].y != a[i - 1].y)			add(a[i].x, a[i].y);		for (int i = 1; i <= n; i++)		if (!dfn[i])			tarjan(i);		for (int i = 1; i <= n; i++)		for (int j = le[i]; j; j = e[j].nxt)			if (in[i] != in[e[j].to]) {   				add_(in[i], in[e[j].to]);				add_b(in[e[j].to], in[i]);				out[in[i]]++;			}		for (int i = 1; i <= n_; i++) {   		if (!out[i]) {   			if (!ans) {   				ans = num[i];				ans_num = i;			}			else {   //有不止一个点没有初度，那肯定互相无法到达，那就肯定没有点了				printf("0");				return 0;			}		}	}		if (dfs(ans_num) == n_) {   		printf("%d", ans);	}	else printf("0");//从这个点出发不可以到所有点		return 0;}

转载地址：http://javh.baihongyu.com/

你可能感兴趣的文章