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>
using namespace std;
const int N = 1e5 + 5;
map<string, int> id;
string a[N], b[N];
vector<int> adj[N];
vector<vector<int>> cicles, pontas;
int prv[N], vis[N], in[N], n_cicle[N], n_ponta[N], leads[N];
int cnt_cicles, cnt_pontas;
bool used[N]; // if a cicle was matched with a 'ponta'
void get_cicles(int v) {
vis[v] = 1;
for (int u : adj[v]) {
if (!vis[u]) {
prv[u] = v;
get_cicles(u);
} else if (vis[u] == 1) {
cicles.push_back({v});
n_cicle[v] = ++cnt_cicles;
int cur = v;
while (cur != u) {
cur = prv[cur];
n_cicle[v] = cnt_cicles;
cicles.back().push_back(cur);
}
cnt_cicles++;
}
}
vis[v] = 2;
}
void get_pontas(int v) {
for (int u : adj[v]) {
if (n_cicle[u]) {
leads[n_ponta[v]] = n_cicle[u];
} else {
n_ponta[u] = n_ponta[v];
pontas.back().push_back(u);
get_pontas(u);
}
}
}
int main() {
int n; cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
id[a[i]], id[b[i]];
}
if (n & 1) {
cout << -1 << '\n';
return 0;
}
int cnt = 0;
for (auto it = id.begin(); it != id.end(); it++) {
it->second = ++cnt;
}
for (int i = 0; i < n; i++) {
adj[id[a[i]]].push_back(id[b[i]]);
in[id[b[i]]]++;
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
get_cicles(i);
}
}
for (int i = 1; i <= n; i++) {
if (!in[i]) {
pontas.push_back({i});
n_ponta[i] = ++cnt_pontas;
get_pontas(i);
}
}
int ans = 0;
for (int i = 0; i < (int) pontas.size(); i++) {
if ((int) pontas[i].size() % 2 != 0 && (int) cicles[leads[i + 1] - 1].size() % 2 != 0) {
pontas[i].pop_back();
cicles[leads[i + 1] - 1].pop_back();
}
// cout << (int) pontas[i].size() << '\n';
ans += ((int) pontas[i].size() + 1) / 2;
}
for (int i = 0; i < (int) cicles.size(); i++) {
// cout << (int) cicles[i].size() << '\n';
ans += ((int) cicles[i].size() == 2 ? 0 : ((int) cicles[i].size() + 1) / 2);
}
cout << ans << '\n';
}
# | 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... |