Submission #44573326

---

Source Code Expand

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define ff(i,s,f) for(int i=s;i<f;i++)
#define fb(i,s,f) for(int i=(s)-1;i>=f;i--)
#define ffi(i,s,f) for(int i=s;i<=f;i++)
#define fbi(i,s,f) for(int i=s;i>=f;i--)
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define ub(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;

const int maxn=2e5+10;

int dsu[maxn];
int siz[maxn];
int cale(int a){
    return dsu[a]==a ? a:dsu[a]=cale(dsu[a]);
}
void join(int a,int b){
    a=cale(a); b=cale(b);
    if(a==b) return;
    if(siz[a]<siz[b]) swap(a,b);
    dsu[b]=a;
    siz[a]+=siz[b];
}

tuple<int,int,char,int> edge[maxn];
int klk=0;
int res[maxn];
bool uradio[maxn];
vector<tuple<int,char,int> > g[maxn];

void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) dsu[i]=i,siz[i]=1;
    for(int i=1;i<=m;i++){
        int u,v; char c;
        cin>>u>>v>>c;
        edge[i]={u,v,c,i};
        g[u].push_back({v,c,i});
        g[v].push_back({u,c,i});
    }
    string s; cin>>s;
    s='#'+s;

    queue<int> bfs;

    for(int i=1;i<=m;i++){
        auto [u,v,c,e]=edge[i];
        if(s[u]!=s[v]) continue;
        if(s[u]!=c) continue;
        if(cale(u)==cale(v)) continue;
        if(!uradio[u]) bfs.push(u);
        if(!uradio[v]) bfs.push(v);
        uradio[u]=true; uradio[v]=true;
        join(u,v);
        res[klk++]=e;
    }

    while(!bfs.empty()){
        int u=bfs.front();
        bfs.pop();
        for(auto [v,c,e]:g[u]){
            if(uradio[v]) continue;
            if(s[v]!=c) continue;
            res[klk++]=e;
            join(u,v);
            bfs.push(v);
            uradio[v]=true;
        }
    }

    bool da=true;
    for(int i=1;i<=n;i++){
        if(!uradio[i]) da=false;
    }
    for(int i=1;i<=m;i++){
        auto [u,v,c,e]=edge[i];
        if(cale(u)==cale(v)) continue;
        join(u,v);
        res[klk++]=e;
    }
    if(da){
        cout<<"Yes\n";
        for(int i=0;i<klk;i++) cout<<res[i]<<" ";
    }else cout<<"No\n";

}

int main(){
    ios;
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

Submission Info

Judge Result