# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
433191 | blue | One-Way Streets (CEOI17_oneway) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <set>
#include <vector>
#include <queue>
using namespace std;
/*
For all pairs (x, y)
If all possible routes from x to y have one or more roads in common, all such roads must be directed.
Repeatedly until there is at least one node with degree = 1:
1. Find a node with degree = 1
2. If that node has no x(+) or y(-) points, set its only edge to 'B'
3. Add all that node's + and - points to a set. Use DSU-style algoithm to combine the sets of its children.
Depending on this, set the direction for its parent edge.
After there are no more nodes with degree = 1, set all remaining edges to 'B'
*/
int main()
{
int n, m;
cin >> n >> m;
vector<int> edge[n+1];
vector<int> edge_count(n+1, 0);
int a[m+1], b[m+1];
for(int j = 1; j <= m; j++)
{
cin >> a[j] >> b[j];
edge[a[j]].push_back(b[j]);
edge_count[a[j]]++;
edge[b[j]].push_back(a[j]);
edge_count[b[j]]++;
}
vector<int> endcount(n+1, 0);
int x, y;
int p;
cin >> p;
for(int i = 1; i <= m; i++)
{
cin >> x >> y;
endcount[x]++;
endcount[y]--;
}
vector<char> res(m+1, 'B');
vector<int> tbv, tbv2;
for(int i = 1; i <= n; i++)
if(edge[i].size() == 1)
tbv.push(i);
while(!tbv.empty())
{
tbv2.clear();
for(int u: tbv)
{
edge_count[u]--;
for(int e: edge[u])
{
int v = a[e] + b[e] - u;
}
}
}
}