【洛谷】P4819 [中山市选] 杀人游戏 的题解

【洛谷】P4819 [中山市选] 杀人游戏 的题解

题目传送门

题解

Tarjan 我可爱的 Tarjan 嘻嘻qaq

枚举每一个点，然后枚举每条出边，如果相连的两个点在同一个强连通分量中，或者 $x$ 所在的强连通分量与 $y$ 所在的强连通分量已经建过边，则需要忽略这条边，接着将 $y$ 所在的强连通分量标记为已建过边，接着统计每个强连通分量的入度，最后清空 vst 数组。继续下一个循环。

主要解释都在代码里了，各位就看看代码吧。

代码

#include <bits/stdc++.h>
#define lowbit(x) x & (-x)
#define endl "\n"
#define maxn 300005
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace fastIO {
inline int read() {
register int x = 0, f = 1;
register char c = getchar();
while (c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
inline void write(int x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
return;
}
}
using namespace fastIO;
struct node{
int to, next;
};
node t[maxn * 2], tc[maxn * 2];
int n, m, tot, totc, num, cnt;
int h[maxn], hc[maxn], dfn[maxn], low[maxn], in[maxn], c[maxn], sum[maxn], vst[maxn], f[maxn], rd[maxn];
stack<int> s;
inline void add(int x, int y){
t[++ tot].to = y;
t[tot].next = h[x];
h[x] = tot;
}
inline void addc(int x, int y) { //建新图
tc[++ totc].to = y;
tc[totc].next = hc[x];
hc[x] = totc;
}
void tarjan(int x) {
dfn[x] = low[x] = ++ num;
s.push(x);
in[x] = 1;
for(int i = h[x]; i; i = t[i].next) {
int y = t[i].to;
if(!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
}
else if(in[y]) low[x] = min(low[x], dfn[y]);
}
if(dfn[x] == low[x]) {
cnt ++;
int y;
do {
y = s.top();
s.pop();
in[y] = 0;
c[y] = cnt;
sum[cnt] ++; //cnt就是这个强连通分量的编号
}while(x != y);
}
}
void clear(int x) {
for(int i = h[x]; i; i =t[i].next) {
vst[c[t[i].to]] = 0;
}
}
bool check(int x){
if (rd[x] or sum[x] != 1) return false; //入度为0并且只有一个点才继续判断
for(int i = hc[x]; i; i = tc[i].next) {
if(rd[tc[i].to] == 1) {
return false; //必须要有其他人认识
}
}
return true;
}
int main() {
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int x, y;
n = read(); m = read();
for(int i = 1; i <= m; i ++) {
x = read(); y = read();
add(x, y);
}
for(int i = 1; i <= n; i ++) {
if(!dfn[i]) {
tarjan(i);
}
}
for(int x = 1; x <= n; x ++) { //枚举每一个点
for(int i = h[x]; i; i = t[i].next) { //枚举每条出边
int y = t[i].to;
if(c[x] == c[y] or vst[c[y]]) continue; //如果相连的两个点在同一个强连通分量中，或者x所在的强连通分量与y所在的强连通分量已经建过边，则需要忽略这条边
vst[c[y]] = 1; //将y所在的强连通分量标记为已建过边
addc(c[x], c[y]); //建边
rd[c[y]] ++; //统计每个强连通分量的入度
}
clear(x); //清空vst数组
}
int ans = 0;
for(int i = 1; i <= cnt; i ++) {
if(!rd[i]) {
ans ++; //统计入度为0的强连通分量的个数
}
}
for(int i = 1; i <= cnt; i ++) {
if(check(i)) { //符合条件
ans --;
break; //这种情况只存在一次，所以如果找到了，就需要break
}
}
printf("%.6lf", double(double(n - ans) / double(n))); //将int转为double，保留小数
return 0;
}

原文地址：https://blog.csdn.net/ZH_qaq/article/details/142577849

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！