Mester / "IOI Válogató 2019" / 5. Banda szétválasztása

#include <iostream>
#include <vector>

#define MAXN 10000
#define MAXM 500000

using namespace std;

vector<int> pontok[MAXN+1];

int N, M;

int tin[MAXN+1];
int low[MAXN+1];
int cnt = 1;

int valasz_komponens = 0, valasz_maxelottunk = 0, valasz = 1;

/* messze nem optimális */

int
tarjan(int current, int parent)
{
    low[current] = tin[current] = cnt++;
    int komponensek = 1;
    int mi = 1;
    int maxelottunk = 0;
    int mogottunk = N - 1;

    bool ap = false;
    for(const auto next : pontok[current]) {
        if(next == parent) continue;

        if(!tin[next]) {
            int gyerekek = tarjan(next, current);

            // hogyha a szülőnkkel egy komponensben vannak
            if(low[next] >= tin[current]){
                maxelottunk = max(maxelottunk, gyerekek);
                mogottunk -= gyerekek;
                komponensek++;
            }
            mi += gyerekek;

            if(tin[current] <= low[next]) {
                ap = true;
            }
            low[current] = min(low[current], low[next]);
        }else{
            low[current] = min(low[current], tin[next]);
        }
    }

    if(ap && (current != 1 || (--komponensek >= 2))) {
        maxelottunk = max(maxelottunk, mogottunk);

        if(komponensek > valasz_komponens || (komponensek == valasz_komponens && maxelottunk <= valasz_maxelottunk)){
            valasz_komponens = komponensek;
            valasz_maxelottunk = maxelottunk;
            valasz = current;
        }
    }
    return mi;
}

int
main()
{
    ios_base::sync_with_stdio(0);

    /* be */
    cin >> N >> M;
    for(int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        pontok[a].push_back(b);
        pontok[b].push_back(a);
    }

    /* do */
    tarjan(1, 1);

    /* ki */
    cout << valasz << endl;

    return 0;
}