import java.io.*;
import java.util.*;
import static java.lang.Math.*;
public class bosses{
static List<Integer>[] adj;
static int[] cost;
static long tot = 0;
static long solve(int i) {
long cost = 1;
for (int x: nadj[i]) cost += solve(x);
tot+=cost;
return cost;
}
static List<Integer>[] nadj;
public static void main(String[] args) throws IOException {
// br = new BufferedReader(new FileReader(".in"));
// out = new PrintWriter(new FileWriter(".out"));
//new Thread(null, new (), "peepee", 1<<28).start();
int n =readInt();
adj = new List[n];
nadj = new List[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
int k= readInt();
while(k-->0) {
adj[readInt()-1].add(i);
}
}
long min = Long.MAX_VALUE;
for (int i = 0; i < n; i++) {
cost = new int[n];
Arrays.fill(cost, -1);
Queue<Integer> q = new ArrayDeque<Integer>();
q.add(i);
for (int j = 0; j < n; j++) nadj[j] = new ArrayList<Integer>();
while (!q.isEmpty()) {
int h = q.poll();
cost[h] = 1;
for (int x: adj[h]) {
if (cost[x] == -1) {
q.add(x);
nadj[h].add(x);
cost[x]=1;
}
}
}
boolean w= true;
for (int j =0 ; j < n; j++) if (cost[i] == -1) w = false;
if (!w) continue;
tot = 0;
solve(i);
min = min(min,tot);
}
out.println(min);
out.close();
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
static StringTokenizer st = new StringTokenizer("");
static String read() throws IOException{return st.hasMoreTokens() ? st.nextToken():(st = new StringTokenizer(br.readLine())).nextToken();}
static int readInt() throws IOException{return Integer.parseInt(read());}
static long readLong() throws IOException{return Long.parseLong(read());}
static double readDouble() throws IOException{return Double.parseDouble(read());}
}
Compilation message
Note: bosses.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
25264 KB |
Output is correct |
2 |
Correct |
48 ms |
22476 KB |
Output is correct |
3 |
Incorrect |
50 ms |
24464 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
25264 KB |
Output is correct |
2 |
Correct |
48 ms |
22476 KB |
Output is correct |
3 |
Incorrect |
50 ms |
24464 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
25264 KB |
Output is correct |
2 |
Correct |
48 ms |
22476 KB |
Output is correct |
3 |
Incorrect |
50 ms |
24464 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |