#include <bits/stdc++.h>
#include <iostream>
#define ll long long
using namespace std;
const int N=500010;
int parents[N];
int getparent(int node){
if ( parents[node]==node)return parents[node]=node;
else return parents[node] = getparent(parents[node]);
}
vector<int> connections[N];
bool covered[N];
int sizep[N];
int main(){
int n,m;cin>>n>>m;
memset(sizep,0,sizeof sizep);
memset(covered,0, sizeof covered);
for (int i=1;i<=n;++i){parents[i]=i;sizep[i]++;}
for (int i = 0;i<m;++i){
char w;int a,b;cin>>a>>b>>w;
int pa=getparent(a);
int pb=getparent(b);
if (w=='T'){
if (pa!=pb){
if (sizep[pa]>sizep[pb]){
sizep[pa]+=sizep[pb];
parents[pb]=pa;
}else{
sizep[pb]+=sizep[pa];
parents[pa]=pb;
}
}
}else{
connections[a].push_back(b);
connections[b].push_back(a);
}
}
int sp = getparent(1);
int c=sizep[sp]-1;
for (int i = 2;i<=n;++i){
int p=getparent(i);
if (p!=sp && !covered[p]){
for (int it : connections[i]){
if (getparent(it)==sp){
c+=sizep[p];
covered[p]=1;break;
}
}
}
}
cout<<c;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |