#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
map<string, int>str_to_int;
int graph[n];
int index=0;
string aa, bb;
int in_degree[n];
memset(graph, -1, sizeof(graph));
memset(in_degree, 0, sizeof(in_degree));
for(int i=0; i<n; i++)
{
cin>>aa>>bb;
if(str_to_int.find(aa)==str_to_int.end())
str_to_int[aa]=index++;
if(str_to_int.find(bb)==str_to_int.end())
str_to_int[bb]=index++;
graph[str_to_int[aa]]=str_to_int[bb];
in_degree[str_to_int[bb]]++;
}
if(n%2==1)
{
cout<<-1;
return 0;
}
bool visited[n];
memset(visited, 0, sizeof(visited));
queue<int>q;
int node;
for(int i=0; i<n; i++)
{
if(visited[i]==0 && i==graph[graph[i]] && graph[i]!=i)
{
visited[i]=1;
visited[graph[i]]=1;
}
else if(visited[i]==0 && in_degree[i]==0)
{
q.push(i);
}
}
int rez=0;
while(!q.empty())
{
node=q.front();
q.pop();
if(!visited[graph[node]])
{
rez++;
in_degree[node]++;
visited[node]=1;
visited[graph[node]]=1;
in_degree[graph[graph[node]]]--;
if(in_degree[graph[graph[node]]]==0)
{
q.push(graph[graph[node]]);
}
}
else
{
in_degree[graph[node]]--;
graph[node]=node;
in_degree[node]++;
}
}
int sz;
for(int i=0; i<n; i++)
{
if(!visited[i] && graph[i]==i)
{
rez++;
visited[i]=1;
}
else if(!visited[i])
{
node=i, sz=0;
while(visited[node]==0)
{
visited[node]=1;
node=graph[node];
sz++;
}
rez+=(sz+1)/2;
}
}
cout<<rez;
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... |