链接
大意:
给一堆点和边,并给出点的颜色,输出每个点能遍历到几个黑点
思路:
1、这些点边里面有拓扑结构, 也有环
2、先处理拓扑排序的一些点,依次遍历无父节点的即可,之后就会剩下环
3、有环的说明每个点都能去到环内任意一点,那么直接就记录一个sum,然后递归求环内黑点,最后把sum赋值给环内所有点即可
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int e[N], ne[N], h[N], idx;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int p[N];
int vis[N];
int in[N];
int f[N];
vector<int> circle; // 为了之后给环里面的东西幅值
int sum;
string s;
void dfs(int u)
{
circle.push_back(u);
if (s[u] == '0')sum++;
vis[u] = 1;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!vis[j])dfs(j);
}
}
void solve()
{
memset(h, -1, sizeof h);
idx = 0;
int n;cin >> n;
for (int i = 1; i <= n; i++)in[i] = f[i] = vis[i] = 0;
for (int i = 1; i <= n; i++)
{
cin >> p[i];
if (i != p[i])
{
add(i, p[i]);
in[p[i]]++;
}
}
cin >> s;
s = " " + s;
// 处理拓扑排序
queue<int>q;
for (int i = 1; i <= n; i++) //拓扑的头 对无环的点
if (!in[i])q.push(i), vis[i] = 1;
while (q.size())
{
int t = q.front();
q.pop();
if (s[t] == '0')f[t] ++;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
in[j] --;
if (!in[j] && !vis[j])q.push(j), vis[j] = 1;
}
}
for (int i = 1; i <= n; i ++)
if (!vis[i])
{
circle.clear();
sum = 0; // 记录环中黑点个数
dfs(i);
for (auto it : circle)f[it] = sum;
}
for (int i = 1; i <= n; i++)
cout << f[i] << ' ';
cout << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
标签:idx,970,int,sum,vis,Codeforces,ne,Sakurako,void
From: https://blog.csdn.net/weixin_47774773/article/details/142766776