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 <bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;
class union_find {
private:
int N;
int components;
vector<int> data;
vector<int> deg;
public:
union_find(int N) : N(N), components(N), data(N, -1), deg(N, 0) {}
int find(int u) {
if(u >= N) return -1;
while(data[u] >= 0) u = data[u];
return u;
}
bool unite(int u, int v) {
if(u >= N || v >= N) return false;
u = find(u);
v = find(v);
if(u == v) return false;
if(data[u] > data[v]) swap(u, v);
data[u] += data[v];
data[v] = u;
--components;
return true;
}
int size(int u) { return -data[find(u)]; }
int getComponentsCount() { return components; }
};
void solve() {
int N, E; cin >> N >> E;
union_find UF(N);
vector<vector<int>> bcns;
bcns.reserve(E);
for(int i = 0; i < E; i++) {
int U, V; cin >> U >> V;
char T; cin >> T;
--U, --V;
if(T == 'T') UF.unite(U, V);
else bcns.push_back({U,V});
}
set<int> rep;
for(int i = 0; i < N; i++) {
rep.insert(UF.find(i));
}
vector<int> deg(N);
set<pair<int,int>> done;
for(auto &cns : bcns) if(
UF.find(cns[0])^UF.find(cns[1]) &&
done.find({UF.find(cns[0]), UF.find(cns[1])}) == done.end()
) {
deg[UF.find(cns[0])]++;
deg[UF.find(cns[1])]++;
done.insert({UF.find(cns[0]), UF.find(cns[1])});
}
set<int> work;
for(auto city : rep) {
if(deg[city] == UF.getComponentsCount() - 1) {
work.insert(city);
}
}
int ans = 0;
for(int i = 0; i < N; i++) {
if(work.find(UF.find(i)) != work.end()) {
++ans;
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int test_cases = 1;
// cin >> test_cases;
for(int test_case = 1; test_case <= test_cases; test_case++) {
// cout << "Case #" << test_case << ": ";
solve();
}
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... |