TravelingMerchant

Mr. Lawrence is a traveling merchant who travels between cities and resells products. Basically, to earn from it, he needs to buy products at a very low price and sell them at a higher price. Your task is to tell him whether there exists an endless traveling path that can earn money all the time.

To make things simple, suppose there are ${n}$ cities named from ${0}$ to ${n-1}$ and ${m}$ undirected roads each of which connecting two cities. Mr. Lawrence can travel between cities along the roads. Initially he is located at city ${0}$ and each of the city ${i}$ has a starting price $c_i$ , either $\text{Low}$ or $\text{High}$ . Due to the law of markets, the price status at city ${i}$ will change (i.e. $\text{High}$ price will become $\text{Low}$ price, or vice versa) after he departs for a neighboring city ${j}$ from ${i}$ . (City ${j}$ is a neighboring city of city ${i}$ when one of the ${m}$ roads connects city ${i}$ and city ${j}$ .) For some reasons (e.g. product freshness, traveling fee, tax), he must:

Start at city ${0}$ and buy products at city ${0}$ . It is guaranteed that $c_0$ is $\text{Low}$ .
When he arrives some city, he either sells products or buys products. It is not allowed for him to do nothing before he leaves the city.
After buying products at some city ${i}$ , he must travel to some neighboring city ${j}$ whose price $c_j$ is $\text{High}$ and sell the products at city ${j}$ .
After selling products at some city ${i}$ , he must travel to some neighboring city ${j}$ whose price $c_j$ is $\text{Low}$ and buy the products at city ${j}$ .

As a result, the path will look like an alternation between buy at low price and sell at high price.

An endless earning path is defined as a path consisting of an endless sequence of cities $p_0, p_1,\dots$ where city $p_i$ and city $p_{i+1}$ has a road, $p_0=0$ , and the price alternates, in other words $c_{p_{2k}}=\text{Low}$ (indicates a buy-in) and $c_{p_{2k+1}}=\text{High}$ (indicates a sell-out) for $k \geq 0$ . Please note here $c_{p_i}$ is the price when arriving city $p_i$ and this value may be different when he arrives the second time.

Your task is to determine whether there exists any such path.

There are several test cases. The first line contains a positive integer ${T}$ indicating the number of test cases. Each test case begins with two positive integers ${n}$ and ${m}$ indicating the number of cities and the number of roads.

The next line is a string ${c}$ of length ${n}$ containing $\text H$ or $\text L$ . The ${i}$ -th ( $0\le i<n$ ) charactor of ${c}$ is $\text H$ if the starting price $c_i$ at city ${i}$ is $\text{High}$ . The ${i}$ -th ( $0\le i<n$ ) charactor of ${c}$ is ${L}$ if the starting price $c_i$ at city ${i}$ is $\text{Low}$ .

The ${i}$ -th line ( $1\le i\le m$ ) of the following ${m}$ lines contains two different cities $u_i$ and $v_i$ , indicating a road between $u_i$ and $v_i$ .

The sum of the values of ${n}$ over all test cases is no more than ${200,000}$ . The sum of the values of ${m}$ over all test cases is no more than ${200,000}$ . For each test case, $c_i\in\{\text{H},\text{L}\}$ holds for each $i\in \{0, \ldots, n-1\}$ . $c_0$ is always ${L}$ . $0\leq u_i,v_i<n$ and $u_i\neq v_i$ hold for each $i\in \{1,\ldots, m\}$ . No two roads connect the same pair of cities.

#include<bits/stdc++.h> using namespace std; #define N 400005 #define pb push_back int T,n,m,cntV,dfn[N],low[N],fa[N],st[N],sz[N]; char a[N];vector<int> e1[N],e2[N]; struct Edge {int u,v;}e[N]; void Tarjan(int u,int f) { dfn[u]=low[u]=++dfn[0];st[++st[0]]=u; for(int i=0,v;i<e1[u].size();++i) { v=e1[u][i];if(v==f) continue; if(!dfn[v]) { Tarjan(v,u);low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]) { e2[u].pb(++cntV);e2[cntV].pb(u);e2[v].pb(cntV);e2[cntV].pb(v); while(st[st[0]]!=v) e2[st[st[0]]].pb(cntV),e2[cntV].pb(st[st[0]--]);--st[0]; } }else low[u]=min(low[u],dfn[v]); } } void dfs(int u,int f) { dfn[u]=++dfn[0];sz[u]=1;fa[u]=f; for(int i=0,v;i<e2[u].size();++i) {v=e2[u][i];if(!dfn[v]) dfs(v,u),sz[u]+=sz[v];} } void slv() { scanf("%d %d %s",&n,&m,a+1); for(int i=1;i<=cntV;++i) e2[i].clear();cntV=n; dfn[0]=0;for(int i=1;i<=n;++i) dfn[i]=0,e1[i].clear(); for(int i=1,u,v;i<=m;++i) { scanf("%d %d",&u,&v);++u;++v;e[i]=(Edge) {u,v}; if(a[u]^a[v]) e1[u].pb(v),e1[v].pb(u); }Tarjan(1,0);for(int i=1;i<=cntV;++i) dfn[i]=sz[i]=0;dfs(1,0); for(int i=1,u,v;i<=m;++i) if(a[e[i].u]==a[e[i].v]) { u=e[i].u;v=e[i].v;if(!dfn[u] || !dfn[v]) continue; if(u==1 || v==1) {puts("yes");return;}u=fa[e[i].u];v=fa[e[i].v]; if(dfn[u]>=dfn[v] && dfn[u]<dfn[v]+sz[v]) {puts("yes");return;} if(dfn[v]>=dfn[u] && dfn[v]<dfn[u]+sz[u]) {puts("yes");return;} }puts("no"); } int main() {scanf("%d",&T);while(T--) slv();}

详情