G. Orientation of Edges
time limit per test3 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Vasya has a graph containing both directed (oriented) and undirected (non-oriented) edges. There can be multiple edges between a pair of vertices.
Vasya has picked a vertex s from the graph. Now Vasya wants to create two separate plans:
to orient each undirected edge in one of two possible directions to maximize number of vertices reachable from vertex s;
to orient each undirected edge in one of two possible directions to minimize number of vertices reachable from vertex s.
In each of two plans each undirected edge must become directed. For an edge chosen directions can differ in two plans.
Help Vasya find the plans.
Input
The first line contains three integers n, m and s (2 ≤ n ≤ 3·105, 1 ≤ m ≤ 3·105, 1 ≤ s ≤ n) — number of vertices and edges in the graph, and the vertex Vasya has picked.
The following m lines contain information about the graph edges. Each line contains three integers ti, ui and vi (1 ≤ ti ≤ 2, 1 ≤ ui, vi ≤ n, ui ≠ vi) — edge type and vertices connected by the edge. If ti = 1 then the edge is directed and goes from the vertex ui to the vertex vi. If ti = 2 then the edge is undirected and it connects the vertices ui and vi.
It is guaranteed that there is at least one undirected edge in the graph.
Output
The first two lines should describe the plan which maximizes the number of reachable vertices. The lines three and four should describe the plan which minimizes the number of reachable vertices.
A description of each plan should start with a line containing the number of reachable vertices. The second line of a plan should consist of f symbols ‘+’ and ‘-‘, where f is the number of undirected edges in the initial graph. Print ‘+’ as the j-th symbol of the string if the j-th undirected edge (u, v) from the input should be oriented from u to v. Print ‘-‘ to signify the opposite direction (from v to u). Consider undirected edges to be numbered in the same order they are given in the input.
If there are multiple solutions, print any of them.
Examples
input
2 2 1
1 1 2
2 2 1
output
2
-
2
+
input
6 6 3
2 2 6
1 4 5
2 3 4
1 4 1
1 3 1
2 2 3
output
6
++-
2
+-+
题目链接：CF 2017-2018 NEERC G. Orientation of Edges
最大应该比较好做，从$S$开始$BFS$即可，遇到有向边就走，遇到无向边也走就行了，记得储存一下此时的答案就好；然后是最小的点数，感觉是先只对有向边构成的图$BFS$出$S$可到达的点，然后枚举无向边$(u,v)$，应该有两种情况：$u$与$v$有一个点可达或者两者均不可达，前者的话肯定是要从不可达指向可达的点，这样才能把这条边返回去不增加任何点数，后者的话随意吧，由于前者这种情况的存在，后者实际上两个点应该是不会被$s$连通的，那么方向就保持原来的方向好了。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 3e5 + 7;
struct edge
{
int from, to, nxt, id;
int flag;
edge() {}
edge(int _from, int _to, int _nxt, int _id, int _flag): from(_from), to(_to), nxt(_nxt), id(_id), flag(_flag) {}
} E[N << 1];
int head[N], tot;
int A[N], B[N];
int n, m, s;
bitset<N>vis;
void init()
{
CLR(A, -1);
CLR(B, -1);
CLR(head, -1);
tot = 0;
}
inline void add(int s, int t, int id, int flag)
{
E[tot] = edge(s, t, head[s], id, flag);
head[s] = tot++;
if (flag == 2)
{
E[tot] = edge(t, s, head[t], id, -flag);
head[t] = tot++;
}
}
void bfs()
{
vis.reset();
queue<int>Q;
Q.push(s);
vis[s] = 1;
while (!Q.empty())
{
int u = Q.front();
Q.pop();
for (int i = head[u]; ~i; i = E[i].nxt)
{
int v = E[i].to;
if (E[i].flag == 1)
{
if (!vis[v])
{
vis[v] = 1;
Q.push(v);
}
}
else
{
if (!vis[v])
{
vis[v] = 1;
Q.push(v);
A[E[i].id] = E[i].flag < 0 ? 0 : 1;
}
}
}
}
}
void bfs2()
{
vis.reset();
queue<int>Q;
Q.push(s);
vis[s] = 1;
while (!Q.empty())
{
int u = Q.front();
Q.pop();
for (int i = head[u]; ~i; i = E[i].nxt)
{
int v = E[i].to;
if (E[i].flag != 1)
continue;
if (!vis[v])
{
vis[v] = 1;
Q.push(v);
}
}
}
}
int main(void)
{
int t, a, b, i;
while (~scanf("%d%d%d", &n, &m, &s))
{
init();
int unid = 0;
for (i = 0; i < m; ++i)
{
scanf("%d%d%d", &t, &a, &b);
if (t == 2)
{
++unid;
add(a, b, unid, 2);
}
else
add(a, b, 0, 1);
}
bfs();
printf("%d\n", vis.count());
for (i = 1; i <= unid; ++i)
printf("%c", A[i] ? '+' : '-');
puts("");
bfs2();
printf("%d\n", vis.count());
for (i = 0; i < tot; i++)
{
if (E[i].flag != 1 && E[i].flag > 0)
{
int v = E[i].to, u = E[i].from;
if (vis[u] && !vis[v])
B[E[i].id] = 0;
else
B[E[i].id] = 1;
}
}
for (i = 1; i <= unid; ++i)
printf("%c", B[i] ? '+' : '-');
puts("");
}
return 0;
}