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;
vector<int> g[N] , adj[N] , cy;
map<string , int> mp;
int ans , n , num , len , cnt;
bool deg[N] , vis[N] , make_rel[N] , ch = 1;
void dfs(int ver){
vis[ver] = 1;
len++;
for(int i : g[ver]){
if(vis[i]) continue;
dfs(i);
}
}
void dfs2(int ver){
vis[ver] = 1;
for(int i : adj[ver]){
if(vis[i]) continue;
dfs2(i);
if(!make_rel[i] && !make_rel[ver]) make_rel[i] = make_rel[ver] = 1;
}
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 0 ; i < n ; i++){
string a , b;
cin >> a >> b;
if(mp.find(a) == mp.end()) mp[a] = num++;
if(mp.find(b) == mp.end()) mp[b] = num++;
g[mp[a]].push_back(mp[b]);
adj[mp[b]].push_back(mp[a]);
deg[mp[b]] = 1;
}
if(n & 1){
cout << -1 << '\n';
return 0;
}
for(int i = 0 ; i < n ; i++)
ch &= deg[i];
if(ch){
for(int i = 0 ; i < n ; i++){
if(vis[i]) continue;
len = 0;
dfs(i);
if(len == 2) continue;
ans += len / 2;
if(len & 1) ans++;
}
cout << ans << '\n';
return 0;
}
for(int i = 0 ; i < n ; i++)
if(g[i][0] == i)
dfs2(i);
for(int i = 0 ; i < n ; i++)
if(make_rel[i])
cnt++;
ans = n - cnt;
ans += cnt / 2;
cout << ans << '\n';
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... |