80???
查看原帖
80???
482610
Mortidesperatslav楼主2024/3/12 21:14
#include<bits/stdc++.h>
using namespace std;
#define mxn 114514
int low[mxn], dfn[mxn], col[mxn], f[mxn], d[mxn], el[mxn], er[mxn];
int n, m, cnt, ccnt, ncnt;
bool vis[mxn];
vector<int> G[mxn], NG[mxn];
stack<int> s;
void tarjan(int u, int f){
	dfn[u] = low[u] = ++cnt;
	s.push(u);
	vis[u] = 1;
	for (auto &v : G[u]){
		if (v == f)
			continue;
		if (!dfn[v]){
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
		}else if (vis[v])
			low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u]){
		ccnt++;
		while (!s.empty()){
			int v = s.top();
			s.pop();
			vis[v] = 0;
			col[v] = ccnt;
			if (u == v)
				break;
		}
	}
}
void dfs(int u, int ff){
	d[u] = d[ff] + 1;
	for (auto v : NG[u])
		if (v != ff){
			dfs(v, u);
			f[u] += f[v];
		}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
		el[i] = u;
		er[i] = v;
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			tarjan(i, 0); 
	for (int i = 1; i <= n; i++)
		for (auto v : G[i])
			if (col[i] != col[v]){
				NG[col[i]].push_back(col[v]);
				NG[col[v]].push_back(col[i]); 
			}
	int q;
	cin >> q;
	while (q--){
		int u, v;
		cin >> u >> v;
		f[col[u]]++;
		f[col[v]]--;
	}
	for (int i = 1; i <= ccnt; i++)
		if (!d[i])
			dfs(i, 0);
	for (int i = 1; i <= m; i++){
		int u = col[el[i]], v = col[er[i]];
		if (u == v)
			cout << "B";
		else{
			if (d[u] > d[v]){
				if (f[u] > 0)
					cout << "R";
				else if (f[u] == 0)
					cout << "B";
				else
					cout << "L";
			}else{
				if (f[v] > 0)
					cout << "L";
				else if (f[v] == 0)
					cout << "B";
				else
					cout << "R";
			}
		}
	}
}
2024/3/12 21:14
加载中...