转载请注明出处:http://tokitsukaze.live/

题目链接:http://codeforces.com/problemset/problem/1027/F


题意:给n条边,每个点的编号范围[1,1e9],求一个点集,使每条边至少有一个点在这个点集里,求点集中最大编号最小。不可行输出-1。


题解:
对于一个连通块:
1.如果没有环,其实就是树,取次大的点。
2.如果只有1个环,其实就是基环树,取最大的点。
3.如果有2个以上的环,直接输出-1。

先对点离散化,然后用并查集搞搞,判每个连通块有几个环。如果可行,对每个连通块判断是情况1还是情况2,然后取max就是答案。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_PERMIT_BACKWARD_HASH
#include <ext/hash_map>
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
void go();
int main(){
#ifdef tokitsukaze
freopen("TEST.txt","r",stdin);
#endif
go();return 0;
}
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=2e6+10;
const ll mod=1e9+7;
/********************************* head *********************************/
struct dsu
{
int pre[MAX];
void init(int n)
{
int i;
for(i=1;i<=n;i++)
{
pre[i]=i;
}
}
int find(int x)
{
if(pre[x]!=x) pre[x]=find(pre[x]);
return pre[x];
}
int merge(int a,int b)
{
int ra,rb;
ra=find(a);
rb=find(b);
if(ra!=rb) pre[ra]=rb;
if(ra!=rb) return 0;
else return ra;
}
}dsu;
int cnt[MAX],v[MAX],belong[MAX];
priority_queue<int> q[MAX];
void go()
{
int n,i,a,b,tot,tmp,ans,flag;
while(read(n))
{
tot=0;
hash_map<int,int> mp;
dsu.init(2*n);
for(i=1;i<=2*n;i++) belong[i]=cnt[i]=0;
for(i=1;i<=n;i++)
{
read(a,b);
if(!mp[a])
{
mp[a]=++tot;
v[tot]=a;
}
a=mp[a];
if(!mp[b])
{
mp[b]=++tot;
v[tot]=b;
}
b=mp[b];
tmp=dsu.merge(a,b);
if(tmp) belong[tmp]++;
}
for(i=1;i<=tot;i++) cnt[dsu.find(i)]+=belong[i];
flag=0;
for(i=1;i<=tot;i++)
{
if(cnt[i]>=2) flag=1;
while(!q[i].empty()) q[i].pop();
}
if(flag)
{
puts("-1");
continue;
}
ans=0;
for(i=1;i<=tot;i++)
{
tmp=dsu.find(i);
if(sz(q[tmp])<2) q[tmp].push(-v[i]);
else
{
if(v[i]>-q[tmp].top())
{
q[tmp].pop();
q[tmp].push(-v[i]);
}
}
}
for(int it=1;it<=tot;it++)
{
if(sz(q[it])==0) continue;
tmp=q[it].top();
q[it].pop();
if(cnt[it]==0)
{
if(sz(q[it])>=1) ans=max(ans,-tmp);
else ans=max(ans,-q[it].top());
}
else if(cnt[it]==1) ans=max(ans,-q[it].top());
}
printf("%d\n",ans);
}
}