AcWing 164. 可达性统计
原题链接
中等
作者:
sicau
,
2020-01-31 11:41:27
,
所有人可见
,
阅读 672
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.BitSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) {
InputStream is = System.in;
OutputStream os = System.out;
InputReader in = new InputReader(is);
PrintWriter out = new PrintWriter(os);
Task1 solver = new Task1();
solver.solve(in, out);
out.close();
}
static class Task1 {
final int N = 30010;
int[] head = new int[N];
int[] nxt = new int[N];
int[] ver = new int[N];
int[] seq = new int[N];
int[] ind = new int[N];
int[] ans = new int[N];
BitSet[] st = new BitSet[N];
Queue<Integer> q = new LinkedList<Integer>();
int n, m, u, v, tot = 0, idx = 0;
void add(int x, int y) {
ver[++tot] = y; ind[y]++;
nxt[tot] = head[x]; head[x] = tot;
}
void topo() {
for (int i = 1; i <= n; i++) {
if (ind[i] == 0) q.add(i);
}
while(q.size() != 0) {
int now = q.poll();
seq[++idx] = now;
for (int i = head[now]; i != 0; i = nxt[i]) {
int y = ver[i];
if (--ind[y] == 0) {
q.add(y);
}
}
}
}
public void solve(InputReader in, PrintWriter out) {
n = in.nextInt();
m = in.nextInt();
for (int i = 1; i <= m; i++) {
u = in.nextInt();
v = in.nextInt();
add(u, v);
}
topo();
for (int i = 1; i <= n; i++) st[i] = new BitSet(n);
for (int i = idx; i >= 1; i--) {
st[seq[i]].set(seq[i]);
for (int j = head[seq[i]]; j != 0; j = nxt[j]) {
st[seq[i]].or(st[ver[j]]);
}
ans[seq[i]] = st[seq[i]].cardinality();
}
for (int i = 1; i <= n; i++) {
out.println(ans[i]);
}
}
}
static class InputReader {
public BufferedReader br;
public StringTokenizer st;
public InputReader(InputStream is) {
br = new BufferedReader(new InputStreamReader(is));
st = null;
}
public String next() {
while(st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}