「题解」异构体

一道比较简单的分类讨论题……

一 题目

Source : qbxt2019.10.3 T2
Author : zhx
Submit : luogu T101285

描述

你是能看到第二题的friends呢。 ——aoao
众所周知,小葱同学擅长计算,尤其擅长计算组合数,但这个题和组合数没什么关系。

Paradeus是一个新兴的宗教组织,该组织包含了N-1个Nyto,以及一个Mercurows总共NN个人组成。每个Nyto都是被其他某个人传教而进入的Paradeus,Mercurows是宗教的创立者,也就是说Mercurows并没有被任何人拉进组织。
这张记录了每个人是由谁拉进传销组织的记录被视为Paradeus的教义,一直被广为传颂。

然而,随着岁月的流逝, 有不法分子开始对Paradeus的教义发动了攻击。不法分子在Paradeus的教义上添加了一条记录(a, b),代表b是由a介绍入教的。 这条记录的加入导致Nyto们发现教义已经不合法了。 为了复兴教义,教徒们决定找到这条被不法分子加入的记录,并将其删除以恢复教义的荣光。
更具体的说,现在给定N对记录(a_i, b_i)代表a_i是将b_i拉入教的。注意这NN条记录包含了被不法分子添加的那一条。现在我们希望你找到某一条记录,使得删掉这条记录之后剩下的N-1N−1条记录能够形成合法的教义。要注意的是, 教义并没有标注Mercurows,所以任何人都有可能是Mercurows。

输入

第一行一个数代表人数;
接下来N行每行两个数a_i,b_i代表一条记录。

输出

一行一个数代表删掉第几条记录能够使得教义合法。 如果有多种方案, 输出 编号最大 的方案。 数据保证有解。

范围与约定

对于40%的数据,n≤1000;
对于另外20%的数据,可能成为Mercurows的人一定只有一个;
对于100%的数据,1≤N≤10^5。


二 题解

因为题目保证有解,那么正向地考虑构造,实际上就是在一棵树(有向,边从子节点指向父节点)上多连了一条边(也有向)。
我们要拎出一条边,并使图恢复为一颗有根内向树。

先看这条边会改变什么。它一定会使得一个点的出度 +1。那么就意味着可能存在出度为 2 的节点,当然也可能没有(连在根上)。然后如果没有初度为二的节点,图就会是严格的基环内向树;否则有可能有环(不严格的基环外向树)或无环(DAG)。

实际上就 图一~三 这么几种情况:
二(1) 三种情况

对于图一,只需要在换上选最大边;图二,只能选择出度为 2 的节点指向基环内的边;图三,只需要在出度为 2 的节点的两条出边中选最大的那条。然后判环和把环拎出来只需要写个tarjan,然后就做完了。

考场tarjan写锅还能拿80pts可还行?

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
130
131
132
133
134
135
136
137
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;

const int CN = 2e5+5;

class fs{
public: int to,nxt,id;
void init(int t,int n,int i){to = t;nxt = n;id = i;}
}E[CN];
int hd[CN],ecnt = 0;
void add(int x,int y,int z){
E[++ecnt].init(y,hd[x],z);
hd[x] = ecnt;
}

int n;

int de[CN];
bool ChuDuWeiEr(){
for(int i=1;i<=n;i++)
if(de[i] == 2) return true;
return false;
}

bool vis[CN];

/* tarjan */
int dfn[CN],low[CN],idx = 0,stk[CN],top = 0,bel[CN],bcnt = 0;
bool ins[CN];
int tot[CN];
void dfstj(int u){
dfn[u] = low[u] = ++idx;

ins[u] = true;
stk[++top] = u;

for(int k=hd[u];k;k=E[k].nxt){
int v = E[k].to;
if(!dfn[v]){
dfstj(v);
low[u] = min(low[u],low[v]);
}
else if(ins[v]) low[u] = min(low[u], low[v]);
}

if(dfn[u] == low[u]){
bcnt++;
while(true){
int pos = stk[top--];
ins[pos] = false;
bel[pos] = bcnt;
tot[bcnt]++;
if(pos == u) break;
}
}
}
void scc(){
memset(ins,0,sizeof(ins));
memset(tot,0,sizeof(tot));
for(int i=1;i<=n;i++)
if(!dfn[i]) dfstj(i);
}
/* pan huan */
bool PanHuan(){
scc();
for(int i=1;i<=bcnt;i++) if(tot[i] > 1) return true;
return false;
}

/* zhao huan */
bool On[CN];
void GetCir(int &p,int &q){
memset(On,0,sizeof(On));
for(int i=1;i<=bcnt;i++) if(tot[i] > 1) {p = i; break;}
for(int i=1;i<=n;i++) if(bel[i] == p) On[q = i] = true;
}

/* ji huan nei xiang shu */
int MaxEdge = 0;
void dfsst1(int u){
if(vis[u]) return;
vis[u] = true;
for(int k=hd[u];k;k=E[k].nxt){
int v = E[k].to;
if(On[v]){
MaxEdge = max(MaxEdge, E[k].id);
dfsst1(v);
}
}
}
int ST1(){ // 严格基环外向树
int p,q; scc(); GetCir(p,q);

memset(vis,0,sizeof(vis));
dfsst1(q);

return MaxEdge;
}

/* ST2 */
int ST2(){
int Ans = 0;

int st;
for(int i=1;i<=n;i++) if(de[i] == 2) {st = i; break;}

if(!PanHuan()){ // DAG
for(int k=hd[st];k;k=E[k].nxt) Ans = max(Ans, E[k].id);
}
else{ // 不严格基环内向树
int p,q;
GetCir(p,q);
for(int k=hd[st];k;k=E[k].nxt) if(On[E[k].to]) Ans = max(Ans, E[k].id);
}

return Ans;
}

int main()
{
// scan
scanf("%d",&n);
for(int i=1;i<=n;i++){
int a,b; scanf("%d%d",&a,&b); add(b,a,i); de[b]++;
}

// calc
int ans;
if(ChuDuWeiEr()) ans = ST2();
else ans = ST1(); // ji huan nei xiang shu
printf("%d",ans);

return 0;
}
作者

ce-amtic

发布于

2019-10-04

更新于

2020-12-27

许可协议

CC BY-NC-SA 4.0

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×