「题解」异构体

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

一 题目

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）。

实际上就 图一~三 这么几种情况：

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

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

#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;
}