118 lines
2.6 KiB
Java
118 lines
2.6 KiB
Java
package chelper;
|
|
|
|
import java.util.ArrayList;
|
|
import java.util.Arrays;
|
|
import java.util.LinkedList;
|
|
import java.util.List;
|
|
import java.util.Queue;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
import misc.SimpleSavingChelperSolution;
|
|
|
|
|
|
public class G extends SimpleSavingChelperSolution {
|
|
|
|
private List<List<Integer>> directedEdges;
|
|
private List<List<Integer>> undirectedEdgeIds;
|
|
private int[][] undirectedEdges;
|
|
private int n;
|
|
private int m;
|
|
private int s;
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
wrapSolve(testNumber, in, out);
|
|
}
|
|
|
|
@Override
|
|
public void solve(int testNumber) {
|
|
n = in.nextInt();
|
|
m = in.nextInt();
|
|
s = in.nextInt() - 1;
|
|
|
|
directedEdges = new ArrayList<>();
|
|
undirectedEdgeIds = new ArrayList<>();
|
|
|
|
int M = 0;
|
|
undirectedEdges = new int[m][2];
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
directedEdges.add(new ArrayList<>());
|
|
undirectedEdgeIds.add(new ArrayList<>());
|
|
}
|
|
|
|
for (int i = 0; i < m; i++) {
|
|
int t = in.nextInt();
|
|
int a = in.nextInt() - 1;
|
|
int b = in.nextInt() - 1;
|
|
|
|
if (t == 1) { // directed
|
|
directedEdges.get(a).add(b);
|
|
} else {
|
|
undirectedEdges[M][0] = a;
|
|
undirectedEdges[M][1] = b;
|
|
|
|
undirectedEdgeIds.get(a).add(M);
|
|
undirectedEdgeIds.get(b).add(M);
|
|
|
|
M++;
|
|
}
|
|
}
|
|
|
|
boolean[] maxDirs = new boolean[M];
|
|
int maxCount = bfs(maxDirs, true);
|
|
out.println(maxCount);
|
|
for (int i = 0; i < M; i++) {
|
|
out.print(maxDirs[i] ? '+' : '-');
|
|
}
|
|
out.println();
|
|
|
|
boolean[] minDirs = new boolean[M];
|
|
int minCount = bfs(minDirs, false);
|
|
out.println(minCount);
|
|
for (int i = 0; i < M; i++) {
|
|
out.print(minDirs[i] ? '+' : '-');
|
|
}
|
|
out.println();
|
|
}
|
|
|
|
int bfs(boolean[] dirs, boolean invade) {
|
|
Queue<Integer> queue = new LinkedList<>();
|
|
queue.add(s);
|
|
|
|
boolean[] visited = new boolean[n];
|
|
visited[s] = true;
|
|
|
|
int count = 1;
|
|
|
|
while (!queue.isEmpty()) {
|
|
int v = queue.poll();
|
|
|
|
for (int i : undirectedEdgeIds.get(v)) {
|
|
int u = undirectedEdges[i][0] == v ? undirectedEdges[i][1] : undirectedEdges[i][0];
|
|
|
|
if (!invade) {
|
|
dirs[i] = undirectedEdges[i][0] != v;
|
|
continue;
|
|
}
|
|
|
|
if (!visited[u]) {
|
|
dirs[i] = undirectedEdges[i][0] == v;
|
|
visited[u] = true;
|
|
queue.add(u);
|
|
count++;
|
|
}
|
|
}
|
|
|
|
for (int u : directedEdges.get(v)) {
|
|
if (!visited[u]) {
|
|
visited[u] = true;
|
|
queue.add(u);
|
|
count++;
|
|
}
|
|
}
|
|
}
|
|
return count;
|
|
}
|
|
}
|